source: proiecte/Traffic/DijkstraColSmp.java

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

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.Map;
import java.util.Collections;
import java.util.List;
import edu.rit.pj.Comm;
import edu.rit.pj.ParallelRegion;
import edu.rit.pj.ParallelTeam;
import edu.rit.pj.ParallelIteration;

public class DijkstraColSmp {

        private final static Integer infinity = 2000;
        static int len = 0;
        static Graph g;
        static Map<Vertex, Integer> distFromSource;
        static Map<Vertex, Vertex> previousNode;
        static Map<Vertex, Integer> unvisitedNodes;
        static Vertex currentNode;

        /**
         * @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{
                Comm.init (args);
                double begin = System.currentTimeMillis();
                String fileName = null;
                Vertex source = null;
                Vertex destination = null;
                if (args.length == 3) {
                        fileName = args[0];
                        source = new Vertex(Integer.parseInt(args[1]));
                        destination = new Vertex(Integer.parseInt(args[2]));
                } else {
                        System.err.println("Invalid command-line arguements");
                        System.exit(0);
                }

                List<Vertex> vertices = Collections.synchronizedList( new ArrayList<Vertex>() );
                ArrayList<Edge> edges = new ArrayList<Edge>();
                try {
                        BufferedReader in = new BufferedReader(new FileReader(fileName));
                        String line = in.readLine();
                        len = Integer.parseInt( line );
                        while ((line = in.readLine()) != null) {
                                Scanner scan = new Scanner( line );
                                Vertex start = new Vertex( scan.nextInt() );
                                Vertex end = new Vertex( scan.nextInt() );
                                if( !vertices.contains( start ) ) vertices.add( start );
                                if( !vertices.contains( end ) ) vertices.add( end );
                                edges.add( new Edge( start, end, scan.nextInt() ) );
                        }
                        in.close();
                } catch( Exception e ) {
                        e.printStackTrace();
                }
                
                g = new Graph( vertices, edges );
                
                //*** Dijkstra's Algorithm ***\\
                distFromSource = new TreeMap<Vertex, Integer>();
                previousNode = new TreeMap<Vertex, Vertex>();
                unvisitedNodes = new TreeMap<Vertex, Integer>();
                for( Vertex v : g.getVertices() ) {
                        distFromSource.put( v, infinity );
                        previousNode.put( v, null );
                        unvisitedNodes.put( v, null );
                }
                distFromSource.put(source, 0);
                
                new ParallelTeam().execute( new ParallelRegion()
                        {
                        public void run() throws Exception
                        {
                                for( Vertex v : unvisitedNodes.keySet() ) {
                                        currentNode = v;
                                        for( Vertex v2 : unvisitedNodes.keySet() ) {
                                                if( distFromSource.get( v2 ) < distFromSource.get( currentNode ) && unvisitedNodes.get( v2 ) == null )
                                                        currentNode = v2;
                                        }
                                        unvisitedNodes.put( currentNode, new Integer( 1 ) );
                                        execute( g.getEdgesContaining( currentNode ), new ParallelIteration<Edge>()
                                                {
                                                public void run( Edge e )
                                                        {
                                                        int newDist = distFromSource.get( currentNode ) + e.getDistance();
                                                        Vertex otherVertex = e.getOtherVertex( currentNode );
                                                        if( newDist < distFromSource.get( otherVertex ) ) {
                                                                distFromSource.put( otherVertex, newDist );
                                                                previousNode.put( otherVertex, currentNode );
                                                                }
                                                        }
                                                });
                                        }
                                }
                        });
                
                Vertex prev = previousNode.get( destination );
                String output = "[" + destination.getName() + "]";
                while( !source.equals( prev ) ) {
                        output = "[" + prev.getName() + "] -> " + output;
                        prev = previousNode.get( prev );
                }
                output = "[" + source.getName() + "] -> " + output + " (Total Distance = " + distFromSource.get( destination ) + ")";
                System.out.println( output );
                double end = System.currentTimeMillis();
                System.out.println("Runing time: "+ (end - begin));
        }

}