CSC212 Dijkstra's Shortest Path

--D. Thiebaut (talk) 09:03, 19 November 2014 (EST)

---

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex> {
	public final int Id;
	public Edge[] adj;
	public double minDistance = Double.POSITIVE_INFINITY;
	public Vertex predecessor;
	
	public Vertex( int i ) { Id = i; }
	public String toString() { return Id+" "; }
	public int compareTo(Vertex other) {
		return Double.compare(minDistance, other.minDistance);
	}
}

class Edge {
	public final Vertex source;
	public final Vertex dest;
	public final double weight;

	public Edge(Vertex argSource, Vertex argTarget, double argWeight) {
		source = argSource;
		dest = argTarget;
		weight = argWeight;
	}
}

public class Graph2 {
	Vertex[] vertices;
	
	Graph2() {
		vertices = null;
	}
	
	public static void dijkstraPaths(Vertex source) {
		source.minDistance = 0.;
		PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
		vertexQueue.add(source);

		while ( !vertexQueue.isEmpty() ) {
			Vertex u = vertexQueue.poll();

			// Visit each edge emanating from u
			for ( Edge e : u.adj ) {
				Vertex v = e.dest;
				double weight = e.weight;
				double distanceThroughU = u.minDistance + weight;
				if (distanceThroughU < v.minDistance) {
					vertexQueue.remove(v);
					v.minDistance = distanceThroughU;
					v.predecessor = u;
					vertexQueue.add(v);
				}
			}
		}
	}

	public static List<Vertex> getShortestPathTo(Vertex target) {
		List<Vertex> path = new ArrayList<Vertex>();
		for (Vertex vertex = target; vertex != null; vertex = vertex.predecessor)
			path.add(vertex);
		Collections.reverse(path);
		return path;
	}

	private static Vertex[] generateSampleGraph1() {
		Vertex v0 = new Vertex( 0 ) ;
		Vertex v1 = new Vertex( 1 );
		Vertex v2 = new Vertex( 2 );
		Vertex v3 = new Vertex( 3 );
		Vertex v4 = new Vertex( 4 );

		v0.adj = new Edge[] { new Edge( v0, v1, 5), new Edge( v0, v2, 10),
										new Edge( v0, v3, 8) };
		v1.adj = new Edge[] { new Edge( v1, v0, 5), new Edge( v1, v2, 3),
										new Edge( v1, v4, 7) };
		v2.adj = new Edge[] { new Edge( v2, v0, 10), new Edge( v2, v1, 3) };
		v3.adj = new Edge[] { new Edge( v3, v0, 8), new Edge( v3, v4, 2) };
		v4.adj = new Edge[] { new Edge( v4, v1, 7), new Edge( v4, v3, 2) };
		
		return new Vertex[] { v0, v1, v2, v3, v4 };
	}

	private static Vertex[] generateSampleGraph2() {
		Vertex v0 = new Vertex( 0 ) ;
		Vertex v1 = new Vertex( 1 );
		Vertex v2 = new Vertex( 2 );
		Vertex v3 = new Vertex( 3 );
		Vertex v4 = new Vertex( 4 );
		Vertex v5 = new Vertex( 5 );
		Vertex v6 = new Vertex( 6 );

		v0.adj = new Edge[] { new Edge( v0, v3, 1), new Edge( v0, v6, 1 ) };
		v1.adj = new Edge[] { new Edge( v1, v5, 5), new Edge( v1, v2, 1),
										new Edge( v1, v4, 3) };
		v2.adj = new Edge[] { new Edge( v2, v1, 1), new Edge( v2, v4, 2), 
										new Edge( v2, v6, 5) };
		v3.adj = new Edge[] { new Edge( v3, v0, 1), new Edge( v3, v4, 9) };
		v4.adj = new Edge[] { new Edge( v4, v1, 3), new Edge( v4, v2, 2),
							new Edge( v4, v6, 2), new Edge( v2, v3, 9)};
		v5.adj = new Edge[] { new Edge( v5, v1, 5) }; 
		v6.adj = new Edge[] { new Edge( v6, v2, 5), new Edge( v6, v4, 2), 
							new Edge( v6, v0, 1) };
		
		return new Vertex[] { v0, v1, v2, v3, v4, v5, v6 };
	}

	public void displayShortestPaths( Vertex start ) {
		dijkstraPaths( start );
		for (Vertex v : vertices) {
			System.out.println("Distance to " + v + ": " + v.minDistance);
			List<Vertex> path = getShortestPathTo(v);
			System.out.println("Path: " + path);
		}
	}
	
	private void dot() {
		System.out.println( "digraph G {" );
		for ( Vertex v: vertices ) {
			Edge[] adj = v.adj;
			for ( Edge e : adj ) {
				int source = e.source.Id;
				int dest   = e.dest.Id;
				double weight = e.weight;
				System.out.println( String.format( "%d -> %d [label=\"%1.0f\"];", source, dest, weight ) );
			}
		}
		System.out.println( "}" );
		
	}
	
	public static void main(String[] args) {
		Graph2 G = new Graph2();
		G.vertices = generateSampleGraph1();
		G.displayShortestPaths( G.vertices[5] );
	}

	
}