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