The following code implements the Dijkstra’s Shortest Path Algorithm and further extends is to get all possible shortest paths between two vertices.
For graph representation we make use of JUNG API, its usage, however, is primarily in visualizing the graph and can be extended easily for any other representation as well.
Random Graph Generator code is used to prepare some input graph for this code.
First, our code representation for the vertices in the graph:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
import java.util.List; /** * @author Team Coddicted * */ public class Vertex implements Comparable<Vertex> { /** * Unique ID for every node. */ private int id; /** * Label to be displayed on the vertex (Optional). */ private String label; /** * To hold a previous node in the shortest path. (This would hold a single * node only in one of the possible shortest paths.) */ private Vertex previous; /** * A distance measure for this vertex from source vertex. */ public double sourceDistance = Double.POSITIVE_INFINITY; /** * A List of all previous nodes in all the possible shortest paths. */ private List<Vertex> prev; public Vertex(int id) { this(id, id + ""); } public Vertex(int id, String label) { this.id = id; this.label = label; } @Override public String toString() { return label; } /** * @return the id */ public int getId() { return id; } /** * @return the prev */ public List<Vertex> getPrev() { return prev; } /** * @param prev * the prev to set */ public void setPrev(List<Vertex> prev) { this.prev = prev; } /** * @param id * the id to set */ public void setId(int id) { this.id = id; } /** * @return the label */ public String getLabel() { return label; } /** * @param label * the label to set */ public void setLabel(String label) { this.label = label; } /** * @return the previous */ public Vertex getPrevious() { return previous; } /** * @param previous * the previous to set */ public void setPrevious(Vertex previous) { this.previous = previous; } /** * @return the minDistance */ public double getMinDistance() { return sourceDistance; } /** * @param minDistance * the minDistance to set */ public void setMinDistance(double minDistance) { this.sourceDistance = minDistance; } @Override public int compareTo(Vertex other) { return Double.compare(sourceDistance, other.sourceDistance); } } |
Next, the algorithm implementation for finding the shortest paths:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.PriorityQueue; import java.util.Set; import org.iitj.complex.graph.Vertex; import edu.uci.ics.jung.graph.Graph; /** * @author Team Coddicted * */ public class Dijkstra { private Graph<Vertex, String> g; private Set<List<Vertex>> allShortestPaths; public Dijkstra(Graph<Vertex, String> g) { this.g = g; } private Vertex getSourceFromId(Integer sourceId) { Collection<Vertex> vertices = g.getVertices(); for (Iterator<Vertex> iterator = vertices.iterator(); iterator .hasNext();) { Vertex vertex = (Vertex) iterator.next(); if (vertex.getId() == sourceId) return vertex; } return null; } /** * Computes all shortest paths to all the vertices in the graph using the * Dijkstra's shortest path algorithm. * * @param sourceId * : Starting node from which to find the shortest paths. */ public void computeAllShortestPaths(Integer sourceId) { Vertex source = getSourceFromId(sourceId); source.sourceDistance = 0; PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); vertexQueue.add(source); List<Vertex> prev = null; while (!vertexQueue.isEmpty()) { Vertex u = vertexQueue.poll(); Collection<Vertex> neighbs = g.getNeighbors(u); for (Iterator<Vertex> iterator = neighbs.iterator(); iterator .hasNext();) { Vertex nv = (Vertex) iterator.next(); prev = nv.getPrev(); double weight = 1; double distanceThroughU = u.sourceDistance + weight; if (distanceThroughU < nv.sourceDistance) { vertexQueue.remove(nv); nv.sourceDistance = distanceThroughU; nv.setPrevious(u); vertexQueue.add(nv); prev = new ArrayList<Vertex>(); prev.add(u); nv.setPrev(prev); } else if (distanceThroughU == nv.sourceDistance) { if (prev != null) prev.add(u); else { prev = new ArrayList<Vertex>(); prev.add(u); nv.setPrev(prev); } } } } } /** * @param target * @return A List of nodes in order as they would appear in a shortest path. * (There can be multiple shortest paths present. This method * returns just one of those paths.) */ public List<Vertex> getShortestPathTo(Vertex target) { List<Vertex> path = new ArrayList<Vertex>(); for (Vertex vertex = target; vertex != null; vertex = vertex .getPrevious()) path.add(vertex); Collections.reverse(path); return path; } /** * @param target * @return A set of all possible shortest paths from the source to the given * target. */ public Set<List<Vertex>> getAllShortestPathsTo(Vertex target) { allShortestPaths = new HashSet<List<Vertex>>(); getShortestPath(new ArrayList<Vertex>(), target); return allShortestPaths; } /** * Recursive method to enumerate all possible shortest paths and add each * path in the set of all possible shortest paths. * * @param shortestPath * @param target * @return * */ private List<Vertex> getShortestPath(List<Vertex> shortestPath, Vertex target) { List<Vertex> prev = target.getPrev(); if (prev == null) { shortestPath.add(target); Collections.reverse(shortestPath); allShortestPaths.add(shortestPath); } else { List<Vertex> updatedPath = new ArrayList<Vertex>(shortestPath); updatedPath.add(target); for (Iterator<Vertex> iterator = prev.iterator(); iterator .hasNext();) { Vertex vertex = (Vertex) iterator.next(); getShortestPath(updatedPath, vertex); } } return shortestPath; } } |
Finally, some code to test the above implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.Set; import org.iitj.complex.graph.RandomGraphGeneratorCustomVertex; import org.iitj.complex.graph.Vertex; import edu.uci.ics.jung.graph.Graph; public class ShortestPathTest { /** * @param args */ public static void main(String[] args) { // Generate a graph to test the shortest path implementation. RandomGraphGeneratorCustomVertex rggcv = new RandomGraphGeneratorCustomVertex( 15, 0.4); Graph<Vertex, String> g = rggcv.generateRandomGraph(); // Get the Dijkstra implementation's object Dijkstra d = new Dijkstra(g); // Compute all possible shortest paths from the given source d.computeAllShortestPaths(1); // Display the graph (JUNG based implementation) rggcv.displayGraph(g, 1); // Iterate over all vertices and list // all possible shortest paths to all vertices. Collection<Vertex> vertices = g.getVertices(); Vertex v; int i = 1; for (Iterator<Vertex> iterator = vertices.iterator(); iterator .hasNext();) { v = (Vertex) iterator.next(); System.out.println("Distance to " + v.getId() + ": " + v.sourceDistance); List<Vertex> path = d.getShortestPathTo(v); System.out.println("Path: " + path); System.out.println("---- All Possible Paths ----"); Set<List<Vertex>> allShortestPaths = d.getAllShortestPathsTo(v); for (Iterator<List<Vertex>> iter = allShortestPaths.iterator(); iter .hasNext(); i++) { List<Vertex> p = (List<Vertex>) iter.next(); System.out.println("Path " + i + ": " + p); } i = 1; System.out .print("#####################################################\n\n"); } } } |
The input graph generator code can be obtained from here.
A sample output generated from the above code is shown below:
Red Color node is taken to be source node for calculating shortest paths to the rest of nodes.
Output for this graph is as obtained below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
Distance to 4: 2.0 Path: [1, 10, 4] ---- All Possible Paths ---- Path 1: [1, 8, 4] Path 2: [1, 10, 4] Path 3: [1, 0, 4] ##################################################### Distance to 12: 1.0 Path: [1, 12] ---- All Possible Paths ---- Path 1: [1, 12] ##################################################### Distance to 11: 2.0 Path: [1, 3, 11] ---- All Possible Paths ---- Path 1: [1, 5, 11] Path 2: [1, 3, 11] Path 3: [1, 12, 11] ##################################################### Distance to 6: 2.0 Path: [1, 0, 6] ---- All Possible Paths ---- Path 1: [1, 5, 6] Path 2: [1, 0, 6] Path 3: [1, 12, 6] Path 4: [1, 13, 6] ##################################################### Distance to 9: 2.0 Path: [1, 10, 9] ---- All Possible Paths ---- Path 1: [1, 10, 9] Path 2: [1, 0, 9] ##################################################### Distance to 1: 0.0 Path: [1] ---- All Possible Paths ---- Path 1: [1] ##################################################### Distance to 2: 2.0 Path: [1, 0, 2] ---- All Possible Paths ---- Path 1: [1, 12, 2] Path 2: [1, 0, 2] ##################################################### Distance to 10: 1.0 Path: [1, 10] ---- All Possible Paths ---- Path 1: [1, 10] ##################################################### Distance to 13: 1.0 Path: [1, 13] ---- All Possible Paths ---- Path 1: [1, 13] ##################################################### Distance to 14: 2.0 Path: [1, 3, 14] ---- All Possible Paths ---- Path 1: [1, 3, 14] Path 2: [1, 5, 14] ##################################################### Distance to 8: 1.0 Path: [1, 8] ---- All Possible Paths ---- Path 1: [1, 8] ##################################################### Distance to 7: 2.0 Path: [1, 0, 7] ---- All Possible Paths ---- Path 1: [1, 3, 7] Path 2: [1, 0, 7] Path 3: [1, 12, 7] Path 4: [1, 8, 7] ##################################################### Distance to 3: 1.0 Path: [1, 3] ---- All Possible Paths ---- Path 1: [1, 3] ##################################################### Distance to 0: 1.0 Path: [1, 0] ---- All Possible Paths ---- Path 1: [1, 0] ##################################################### Distance to 5: 1.0 Path: [1, 5] ---- All Possible Paths ---- Path 1: [1, 5] ##################################################### |
Hey There. I found your blog using msn. That is a very neatly written article.
I’ll be sure to bookmark it and come back to read more
of your useful info. Thanks for the post. I will definitely comeback.
very useful
Could you give me this full code file, please?
Hi,
The code presented above is complete. You could simply copy-paste them and make java files as per class names. You should spend at least that much effort 😉
-Thanks