1+ // A Java program for Dijkstra's single source shortest path algorithm.
2+ // The program is for adjacency matrix representation of the graph
3+ import java .util .*;
4+ import java .lang .*;
5+ import java .io .*;
6+
7+ class ShortestPath {
8+ // A utility function to find the vertex with minimum distance value,
9+ // from the set of vertices not yet included in shortest path tree
10+ static final int V = 9 ;
11+ int minDistance (int dist [], Boolean sptSet [])
12+ {
13+ // Initialize min value
14+ int min = Integer .MAX_VALUE , min_index = -1 ;
15+
16+ for (int v = 0 ; v < V ; v ++)
17+ if (sptSet [v ] == false && dist [v ] <= min ) {
18+ min = dist [v ];
19+ min_index = v ;
20+ }
21+
22+ return min_index ;
23+ }
24+
25+ // A utility function to print the constructed distance array
26+ void printSolution (int dist [])
27+ {
28+ System .out .println ("Vertex \t \t Distance from Source" );
29+ for (int i = 0 ; i < V ; i ++)
30+ System .out .println (i + " \t \t " + dist [i ]);
31+ }
32+
33+ // Function that implements Dijkstra's single source shortest path
34+ // algorithm for a graph represented using adjacency matrix
35+ // representation
36+ void dijkstra (int graph [][], int src )
37+ {
38+ int dist [] = new int [V ]; // The output array. dist[i] will hold
39+ // the shortest distance from src to i
40+
41+ // sptSet[i] will true if vertex i is included in shortest
42+ // path tree or shortest distance from src to i is finalized
43+ Boolean sptSet [] = new Boolean [V ];
44+
45+ // Initialize all distances as INFINITE and stpSet[] as false
46+ for (int i = 0 ; i < V ; i ++) {
47+ dist [i ] = Integer .MAX_VALUE ;
48+ sptSet [i ] = false ;
49+ }
50+
51+ // Distance of source vertex from itself is always 0
52+ dist [src ] = 0 ;
53+
54+ // Find shortest path for all vertices
55+ for (int count = 0 ; count < V - 1 ; count ++) {
56+ // Pick the minimum distance vertex from the set of vertices
57+ // not yet processed. u is always equal to src in first
58+ // iteration.
59+ int u = minDistance (dist , sptSet );
60+
61+ // Mark the picked vertex as processed
62+ sptSet [u ] = true ;
63+
64+ // Update dist value of the adjacent vertices of the
65+ // picked vertex.
66+ for (int v = 0 ; v < V ; v ++)
67+
68+ // Update dist[v] only if is not in sptSet, there is an
69+ // edge from u to v, and total weight of path from src to
70+ // v through u is smaller than current value of dist[v]
71+ if (!sptSet [v ] && graph [u ][v ] != 0 && dist [u ] != Integer .MAX_VALUE && dist [u ] + graph [u ][v ] < dist [v ])
72+ dist [v ] = dist [u ] + graph [u ][v ];
73+ }
74+
75+ // print the constructed distance array
76+ printSolution (dist );
77+ }
78+
79+ // Driver method
80+ public static void main (String [] args )
81+ {
82+ /* Let us create the example graph discussed above */
83+ int graph [][] = new int [][] { { 0 , 4 , 0 , 0 , 0 , 0 , 0 , 8 , 0 },
84+ { 4 , 0 , 8 , 0 , 0 , 0 , 0 , 11 , 0 },
85+ { 0 , 8 , 0 , 7 , 0 , 4 , 0 , 0 , 2 },
86+ { 0 , 0 , 7 , 0 , 9 , 14 , 0 , 0 , 0 },
87+ { 0 , 0 , 0 , 9 , 0 , 10 , 0 , 0 , 0 },
88+ { 0 , 0 , 4 , 14 , 10 , 0 , 2 , 0 , 0 },
89+ { 0 , 0 , 0 , 0 , 0 , 2 , 0 , 1 , 6 },
90+ { 8 , 11 , 0 , 0 , 0 , 0 , 1 , 0 , 7 },
91+ { 0 , 0 , 2 , 0 , 0 , 0 , 6 , 7 , 0 } };
92+ ShortestPath t = new ShortestPath ();
93+ t .dijkstra (graph , 0 );
94+ }
95+ }
0 commit comments