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);
}
}
public static void main(String[] args) {
Graph2 G = new Graph2();
G.vertices = generateSampleGraph1();
G.displayShortestPaths( G.vertices[5] );
}
}