Last active
December 18, 2017 18:57
-
-
Save anil477/18e4e021c1097dc36af7d9c1758fbd2b to your computer and use it in GitHub Desktop.
Dijkstra’s shortest path algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// A Java program for Dijkstra's single source shortest path algorithm. | |
// The program is for adjacency matrix representation of the graph | |
import java.util.*; | |
import java.lang.*; | |
import java.io.*; | |
class ShortestPath | |
{ | |
// A utility function to find the vertex with minimum distance value, | |
// from the set of vertices not yet included in shortest path tree | |
static final int V=9; | |
int minDistance(int dist[], Boolean sptSet[]) | |
{ | |
// Initialize min value | |
int min = Integer.MAX_VALUE, min_index=-1; | |
for (int v = 0; v < V; v++) | |
if (sptSet[v] == false && dist[v] <= min) | |
{ | |
min = dist[v]; | |
min_index = v; | |
} | |
return min_index; | |
} | |
// A utility function to print the constructed distance array | |
void printSolution(int dist[], int n) | |
{ | |
System.out.println("Vertex Distance from Source"); | |
for (int i = 0; i < V; i++) | |
System.out.println(i+" to "+dist[i]); | |
} | |
// Funtion that implements Dijkstra's single source shortest path | |
// algorithm for a graph represented using adjacency matrix | |
// representation | |
void dijkstra(int graph[][], int src) | |
{ | |
int dist[] = new int[V]; // The output array. dist[i] will hold | |
// the shortest distance from src to i | |
// sptSet[i] will true if vertex i is included in shortest | |
// path tree or shortest distance from src to i is finalized | |
Boolean sptSet[] = new Boolean[V]; | |
// Initialize all distances as INFINITE and stpSet[] as false | |
for (int i = 0; i < V; i++) | |
{ | |
dist[i] = Integer.MAX_VALUE; | |
sptSet[i] = false; | |
} | |
// Distance of source vertex from itself is always 0 | |
dist[src] = 0; | |
// Find shortest path for all vertices | |
for (int count = 0; count < V-1; count++) | |
{ | |
// Pick the minimum distance vertex from the set of vertices | |
// not yet processed. u is always equal to src in first | |
// iteration. | |
int u = minDistance(dist, sptSet); | |
// Mark the picked vertex as processed | |
sptSet[u] = true; | |
// Update dist value of the adjacent vertices of the | |
// picked vertex. | |
for (int v = 0; v < V; v++) | |
// Update dist[v] only if is not in sptSet, there is an | |
// edge from u to v, and total weight of path from src to | |
// v through u is smaller than current value of dist[v] | |
// check - | |
// 1. if the vertex has not been finalized | |
// 2. if there exists a path | |
// 3. there can be no value greate then v(if it's set to INF). So no need to update | |
// 4. the main conditio | |
if (!sptSet[v] && graph[u][v]!=0 && | |
dist[u] != Integer.MAX_VALUE && | |
dist[u]+graph[u][v] < dist[v]) | |
dist[v] = dist[u] + graph[u][v]; | |
// suppose we want to find minimum distance till a particular node eg at 8 | |
// if(sptSet[8] == true) | |
// break; | |
} | |
// print the constructed distance array | |
printSolution(dist, V); | |
} | |
// Driver method | |
public static void main (String[] args) | |
{ | |
/* Let us create the example graph discussed above */ | |
int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0}, | |
{4, 0, 8, 0, 0, 0, 0, 11, 0}, | |
{0, 8, 0, 7, 0, 4, 0, 0, 2}, | |
{0, 0, 7, 0, 9, 14, 0, 0, 0}, | |
{0, 0, 0, 9, 0, 10, 0, 0, 0}, | |
{0, 0, 4, 14, 10, 0, 2, 0, 0}, | |
{0, 0, 0, 0, 0, 2, 0, 1, 6}, | |
{8, 11, 0, 0, 0, 0, 1, 0, 7}, | |
{0, 0, 2, 0, 0, 0, 6, 7, 0} | |
}; | |
ShortestPath t = new ShortestPath(); | |
t.dijkstra(graph, 0); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment