Difference between revisions of "CSC212 Dijkstra's Shortest Path"
(One intermediate revision by the same user not shown) | |||
Line 22: | Line 22: | ||
public Vertex predecessor; | public Vertex predecessor; | ||
− | public Vertex(int i) { Id = i; predecessor = null; adj= | + | public Vertex(int i) { Id = i; predecessor = null; adj=null; } |
public String toString() { return Id + " "; } | public String toString() { return Id + " "; } | ||
public int compareTo(Vertex other) { | public int compareTo(Vertex other) { |
Latest revision as of 16:56, 4 December 2014
--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;
/**
* Code taken from http://www.algolist.com/code/java/Dijkstra's_algorithm
*/
/**
* Implementation of a Vertex object.
* Each vertex has a unique Id. The first vertex created
* has an Id of 0.
* Each vertex contains a list of edges that emanate from it.
*/
class Vertex implements Comparable<Vertex> {
public final int Id;
public Edge[] adj; // adjacency list for vertex
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex predecessor;
public Vertex(int i) { Id = i; predecessor = null; adj=null; }
public String toString() { return Id + " "; }
public int compareTo(Vertex other) {
return Double.compare(minDistance, other.minDistance);
}
}
/**
* Implementation of an edge. An edge is directed and goes from
* source vertex to dest vertex. It has a real weight.
*/
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;
}
}
/**
* The graph class.
* The graph is simply implemented as an array of vertices. The connections
* between vertices are held in adjacency lists in the vertices.
*
*/
public class Graph2 {
Vertex[] vertices;
/**
* constructor. The graph must be initialized by adding vertices
* and their adjacency list to the Vertex[] vertices.
*/
Graph2() {
vertices = null;
}
/**
* Find the shortest path from source to the other reachable nodes.
* @param source
*/
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);
}
}
}
}
/**
* Return an ArrayList of vertices that go from source (see Dijkstra)
* to target.
* @param target the destination of the path.
* @return an arraylist of vertices
*/
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;
}
/**
* generates a graph with 5 vertices
* @return array of vertices
*/
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 };
}
/**
* generates a graph with 7 vertices
* @return array of vertices
*/
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 };
}
/**
* displays the shortest paths found from the start vertex to ALL
* reachable vertices.
* @param start
*/
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);
}
}
/**
* generate the dot version of the digraph.
*/
private void dot() {
// provided later
}
public static void main(String[] args) {
Graph2 G = new Graph2();
G.vertices = generateSampleGraph1();
// G.displayShortestPaths( G.vertices[5] );
G.dot();
}
}