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