1 | /** |
---|
2 | * Sequential Version of Dijkstra's Algorithm |
---|
3 | */ |
---|
4 | |
---|
5 | import java.io.BufferedReader; |
---|
6 | import java.io.FileReader; |
---|
7 | import java.util.Scanner; |
---|
8 | |
---|
9 | public class DijkstraMatSeq { |
---|
10 | |
---|
11 | private final static Integer infinity = 2000; |
---|
12 | |
---|
13 | /** |
---|
14 | * @param args |
---|
15 | * 0 - Filename where Vertices and Edges are stored |
---|
16 | * @param args |
---|
17 | * 1 - Name of the source vertex |
---|
18 | * @param args |
---|
19 | * 2 - Name of the destination vertex |
---|
20 | */ |
---|
21 | public static void main( String[] args ) { |
---|
22 | long time = -System.currentTimeMillis(); |
---|
23 | String fileName = null; |
---|
24 | int source = 0; |
---|
25 | int destination = 0; |
---|
26 | if (args.length == 3) { |
---|
27 | fileName = args[0]; |
---|
28 | source = Integer.parseInt(args[1]); |
---|
29 | destination = Integer.parseInt(args[2]); |
---|
30 | } else { |
---|
31 | System.err.println("Invalid command-line arguements"); |
---|
32 | System.exit(0); |
---|
33 | } |
---|
34 | |
---|
35 | int[][] graph = null; |
---|
36 | int len = 0; |
---|
37 | try { |
---|
38 | BufferedReader in = new BufferedReader(new FileReader(fileName)); |
---|
39 | String line = in.readLine(); |
---|
40 | len = Integer.parseInt( line ); |
---|
41 | graph = new int[len][len]; |
---|
42 | for( int a = 0; a < len; a++ ) { |
---|
43 | for( int b = 0; b < len; b++ ) { |
---|
44 | graph[a][b] = infinity; |
---|
45 | } |
---|
46 | } |
---|
47 | while ((line = in.readLine()) != null) { |
---|
48 | Scanner scan = new Scanner( line ); |
---|
49 | int pointA = scan.nextInt(); |
---|
50 | int pointB = scan.nextInt(); |
---|
51 | int dist = scan.nextInt(); |
---|
52 | graph[pointA][pointB] = dist; |
---|
53 | graph[pointB][pointA] = dist; |
---|
54 | } |
---|
55 | in.close(); |
---|
56 | } catch( Exception e ) { |
---|
57 | e.printStackTrace(); |
---|
58 | } |
---|
59 | |
---|
60 | //*** Dijkstra's Algorithm ***\\ |
---|
61 | int[] distFromSource = new int[len]; |
---|
62 | int[] previousNode = new int[len]; |
---|
63 | int[] unvisitedNodes = new int[len]; |
---|
64 | for( int i = 0; i < len; i++ ) { |
---|
65 | distFromSource[i] = infinity; |
---|
66 | previousNode[i] = -1; |
---|
67 | } |
---|
68 | distFromSource[source] = 0; |
---|
69 | |
---|
70 | for( int j = 0; j < len; j++ ) { |
---|
71 | int currentNode = j; |
---|
72 | for( int j2 = 0; j2 < len; j2++ ) { |
---|
73 | if( distFromSource[j2] < distFromSource[currentNode] && unvisitedNodes[j2] != 1 ) |
---|
74 | currentNode = j2; |
---|
75 | } |
---|
76 | unvisitedNodes[currentNode] = 1; |
---|
77 | for( int k = j; k < graph[currentNode].length; k++ ) { |
---|
78 | int newDist = distFromSource[currentNode] + graph[currentNode][k]; |
---|
79 | if( newDist < distFromSource[k] ) { |
---|
80 | distFromSource[k] = newDist; |
---|
81 | previousNode[k] = currentNode; |
---|
82 | } |
---|
83 | } |
---|
84 | } |
---|
85 | |
---|
86 | //Print out the output |
---|
87 | int prev = previousNode[destination]; |
---|
88 | String output = "[" + destination + "]"; |
---|
89 | while( source != prev ) { |
---|
90 | output = "[" + prev + "] -> " + output; |
---|
91 | prev = previousNode[prev]; |
---|
92 | } |
---|
93 | output = "[" + source + "] -> " + output + " (Total Distance = " + distFromSource[destination] + ")"; |
---|
94 | System.out.println( output ); |
---|
95 | System.out.println( "Running Time : " + (System.currentTimeMillis() + time) ); |
---|
96 | } |
---|
97 | |
---|
98 | } |
---|