source: proiecte/Traffic/DijkstraMatSmp.java

/**
 * Smp Version of Dijkstra's Algorithm
 */

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Scanner;
import edu.rit.pj.*;

public class DijkstraMatSmp {

        final static Integer infinity = 2000;
        static int[] distFromSource;
        static int[] previousNode;
        static int[] unvisitedNodes;
        static int[][] graph = null;
        static int len = 0;

        /**
         * @param args
         *            0 - Filename where Vertices and Edges are stored
         * @param args
         *            1 - Name of the source vertex
         * @param args
         *            2 - Name of the destination vertex
         */
        public static void main( String[] args ) throws Exception {
                long time = -System.currentTimeMillis();
                Comm.init( args );
                String fileName = null;
                int source = 0;
                int destination = 0;
                if (args.length == 3) {
                        fileName = args[0];
                        source = Integer.parseInt(args[1]);
                        destination = Integer.parseInt(args[2]);
                } else {
                        System.err.println("Invalid command-line arguements");
                        System.exit(0);
                }

                try {
                        BufferedReader in = new BufferedReader(new FileReader(fileName));
                        String line = in.readLine();
                        len = Integer.parseInt( line );
                        graph = new int[len][len];
                        for( int a = 0; a < len; a++ ) {
                                for( int b = 0; b < len; b++ ) {
                                        graph[a][b] = infinity;
                                }
                        }
                        while ((line = in.readLine()) != null) {
                                Scanner scan = new Scanner( line );
                                int pointA = scan.nextInt();
                                int pointB = scan.nextInt();
                                int dist = scan.nextInt();
                                graph[pointA][pointB] = dist;
                                graph[pointB][pointA] = dist;
                        }
                        in.close();
                } catch( Exception e ) {
                        e.printStackTrace();
                }
                
                //*** Dijkstra's Algorithm ***\\
                distFromSource = new int[len];
                previousNode = new int[len];
                unvisitedNodes = new int[len];
                for( int i = 0; i < len; i++ ) {
                        distFromSource[i] = infinity;
                        previousNode[i] = -1;
                }
                distFromSource[source] = 0;
                
                new ParallelTeam().execute( new ParallelRegion() 
                        {
                                public void run() throws Exception {
                                        execute( 0, len-1, new IntegerForLoop()
                                                {
                                                        public void run (int first, int last) {
                                                                for( int j = first; j <= last; j++ ) {
                                                                        int currentNode = j;
                                                                        for( int j2 = 0; j2 < len; j2++ ) {
                                                                                if( distFromSource[j2] < distFromSource[currentNode] && unvisitedNodes[j2] != 1 )
                                                                                        currentNode = j2;
                                                                        }
                                                                        unvisitedNodes[currentNode] = 1;
                                                                        for( int k = j; k < graph[currentNode].length; k++ ) {
                                                                                int newDist = distFromSource[currentNode] + graph[currentNode][k];
                                                                                if( newDist < distFromSource[k] ) {
                                                                                        distFromSource[k] = newDist;
                                                                                        previousNode[k] = currentNode;
                                                                                }
                                                                        }
                                                                }
                                                        }
                                                });
                                }
                        });
                
                //Print out the output
                int prev = previousNode[destination];
                String output = "[" + destination + "]";
                while( source != prev ) {
                        output = "[" + prev + "] -> " + output;
                        prev = previousNode[prev];
                }
                output = "[" + source + "] -> " + output + " (Total Distance = " + distFromSource[destination] + ")";
                System.out.println( output );
                System.out.println( "Running Time : " + (System.currentTimeMillis() + time) );
        }

}