[145] | 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.Map; |
---|
| 11 | import java.util.Collections; |
---|
| 12 | import java.util.List; |
---|
| 13 | import edu.rit.pj.Comm; |
---|
| 14 | import edu.rit.pj.ParallelRegion; |
---|
| 15 | import edu.rit.pj.ParallelTeam; |
---|
| 16 | import edu.rit.pj.ParallelIteration; |
---|
| 17 | |
---|
| 18 | public class DijkstraColSmp { |
---|
| 19 | |
---|
| 20 | private final static Integer infinity = 2000; |
---|
| 21 | static int len = 0; |
---|
| 22 | static Graph g; |
---|
| 23 | static Map<Vertex, Integer> distFromSource; |
---|
| 24 | static Map<Vertex, Vertex> previousNode; |
---|
| 25 | static Map<Vertex, Integer> unvisitedNodes; |
---|
| 26 | static Vertex currentNode; |
---|
| 27 | |
---|
| 28 | /** |
---|
| 29 | * @param args |
---|
| 30 | * 0 - Filename where Vertices and Edges are stored |
---|
| 31 | * @param args |
---|
| 32 | * 1 - Name of the source vertex |
---|
| 33 | * @param args |
---|
| 34 | * 2 - Name of the destination vertex |
---|
| 35 | */ |
---|
| 36 | public static void main(String[] args) throws Exception{ |
---|
| 37 | Comm.init (args); |
---|
| 38 | double begin = System.currentTimeMillis(); |
---|
| 39 | String fileName = null; |
---|
| 40 | Vertex source = null; |
---|
| 41 | Vertex destination = null; |
---|
| 42 | if (args.length == 3) { |
---|
| 43 | fileName = args[0]; |
---|
| 44 | source = new Vertex(Integer.parseInt(args[1])); |
---|
| 45 | destination = new Vertex(Integer.parseInt(args[2])); |
---|
| 46 | } else { |
---|
| 47 | System.err.println("Invalid command-line arguements"); |
---|
| 48 | System.exit(0); |
---|
| 49 | } |
---|
| 50 | |
---|
| 51 | List<Vertex> vertices = Collections.synchronizedList( new ArrayList<Vertex>() ); |
---|
| 52 | ArrayList<Edge> edges = new ArrayList<Edge>(); |
---|
| 53 | try { |
---|
| 54 | BufferedReader in = new BufferedReader(new FileReader(fileName)); |
---|
| 55 | String line = in.readLine(); |
---|
| 56 | len = Integer.parseInt( line ); |
---|
| 57 | while ((line = in.readLine()) != null) { |
---|
| 58 | Scanner scan = new Scanner( line ); |
---|
| 59 | Vertex start = new Vertex( scan.nextInt() ); |
---|
| 60 | Vertex end = new Vertex( scan.nextInt() ); |
---|
| 61 | if( !vertices.contains( start ) ) vertices.add( start ); |
---|
| 62 | if( !vertices.contains( end ) ) vertices.add( end ); |
---|
| 63 | edges.add( new Edge( start, end, scan.nextInt() ) ); |
---|
| 64 | } |
---|
| 65 | in.close(); |
---|
| 66 | } catch( Exception e ) { |
---|
| 67 | e.printStackTrace(); |
---|
| 68 | } |
---|
| 69 | |
---|
| 70 | g = new Graph( vertices, edges ); |
---|
| 71 | |
---|
| 72 | //*** Dijkstra's Algorithm ***\\ |
---|
| 73 | distFromSource = new TreeMap<Vertex, Integer>(); |
---|
| 74 | previousNode = new TreeMap<Vertex, Vertex>(); |
---|
| 75 | unvisitedNodes = new TreeMap<Vertex, Integer>(); |
---|
| 76 | for( Vertex v : g.getVertices() ) { |
---|
| 77 | distFromSource.put( v, infinity ); |
---|
| 78 | previousNode.put( v, null ); |
---|
| 79 | unvisitedNodes.put( v, null ); |
---|
| 80 | } |
---|
| 81 | distFromSource.put(source, 0); |
---|
| 82 | |
---|
| 83 | new ParallelTeam().execute( new ParallelRegion() |
---|
| 84 | { |
---|
| 85 | public void run() throws Exception |
---|
| 86 | { |
---|
| 87 | for( Vertex v : unvisitedNodes.keySet() ) { |
---|
| 88 | currentNode = v; |
---|
| 89 | for( Vertex v2 : unvisitedNodes.keySet() ) { |
---|
| 90 | if( distFromSource.get( v2 ) < distFromSource.get( currentNode ) && unvisitedNodes.get( v2 ) == null ) |
---|
| 91 | currentNode = v2; |
---|
| 92 | } |
---|
| 93 | unvisitedNodes.put( currentNode, new Integer( 1 ) ); |
---|
| 94 | execute( g.getEdgesContaining( currentNode ), new ParallelIteration<Edge>() |
---|
| 95 | { |
---|
| 96 | public void run( Edge e ) |
---|
| 97 | { |
---|
| 98 | int newDist = distFromSource.get( currentNode ) + e.getDistance(); |
---|
| 99 | Vertex otherVertex = e.getOtherVertex( currentNode ); |
---|
| 100 | if( newDist < distFromSource.get( otherVertex ) ) { |
---|
| 101 | distFromSource.put( otherVertex, newDist ); |
---|
| 102 | previousNode.put( otherVertex, currentNode ); |
---|
| 103 | } |
---|
| 104 | } |
---|
| 105 | }); |
---|
| 106 | } |
---|
| 107 | } |
---|
| 108 | }); |
---|
| 109 | |
---|
| 110 | Vertex prev = previousNode.get( destination ); |
---|
| 111 | String output = "[" + destination.getName() + "]"; |
---|
| 112 | while( !source.equals( prev ) ) { |
---|
| 113 | output = "[" + prev.getName() + "] -> " + output; |
---|
| 114 | prev = previousNode.get( prev ); |
---|
| 115 | } |
---|
| 116 | output = "[" + source.getName() + "] -> " + output + " (Total Distance = " + distFromSource.get( destination ) + ")"; |
---|
| 117 | System.out.println( output ); |
---|
| 118 | double end = System.currentTimeMillis(); |
---|
| 119 | System.out.println("Runing time: "+ (end - begin)); |
---|
| 120 | } |
---|
| 121 | |
---|
| 122 | } |
---|