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;
/**
 * 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;	}
	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() {
		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] );
		G.dot();
	}

}