The Dijkstra's algorithm is a possible solution for the shortest path problem.

This problem concerns a weighted graph, where all the edges have an assigned "weight", a real number. Given a starting vertex v and an ending vertex u, we want to define (if present) the path from v to u for which the total weight is minimum. The path's weight is easily found by summing up all the weights along the path. Actually, the algorithm only computes this minimum weight, not the actual path, which requires some more programming to be deduced, and graphical libraries to be displayed.

My code will work on a generalization of the shortest path problem: given only a starting vertex, it finds out the minimum necessary weight from that vertex to all the other ones in the graph. It has been demonstrated that the best solution to the shortest path problem in particular is no better than the solution to this more general version.

Let's start with some assumption that will make the problem (and my code) a lot easier. First, all the weights in the graph will be positive numbers; negative values can present a serious issue if circular paths are generated.

Second, for simplicity, I'm using a directed graph; that is, every edge defines a direction from two vertices (from a source to a target) and can't go back unless I define a totally different edge going back the other way.

Third, if no path is present between two vertices, the minimum weight is set to the Java constant Double.POSITIVE_INFINITY.

Let's proceeed with a brief explanation of the algorithm. This is quite complex, so if you don't know the basis, I recommend you find some more precise article.

An important property is that the shortest path problem has an optimal substructure: a subpath of a shortest path is a shortest path too.

Plus, let's call s the starting vertex and d[v] the distance of some generic vertex v from s. The distance is the minimum weight from s to v.

The algorithm starts by initializing some data structures. A priority queue Q (the Vector in my code) is filled with all the vertices. Their initial distances is 0 for s (of course) and +infinity for the other ones.

The general definition uses a set S, at first empty, then filled with the vertices. I don't really need that, but I use an array to store the distances for each vertex: this is because the entries in the priority queue will be removed as the algorithm proceeds, so I need a place to save my results. The vertex number is used as an index in the array.

While the priority queue isn't empty, the minimum vertex u is extracted, the vertex with the minimum distance so far. Then a list of all the vertices that can be reached from u is obtained (adjacency list).

For each element v in the adjacency list, an operation called "relaxation" is performed. First, a note: if v had no ingoing edge, it wouldn't be within reach, therefore its distance will never be updated and will stay infinity until the end of the loop.

If I can reach v, I can take a certain number of ways: the way coming from u, with a weight of d[u] + w(u,v), and other ways coming from other edges, if there are other edges. Along several instances of the loop, the algorithm will simply decide what's the best one.

But it won't do it immediately, because it doesn't consider v alone but the previous step to reach it. So d[v] can be updated several times during the algorithm, following the best paths that it has been creating.

In the code, I use a free Java library called jgrapht. Without the library, which can be downloaded from the official site of the project, and some adjustments to the $CLASSPATH, you won't be able to compile the code.

First, a random graph is created, composed of 5 integer vertices numbered from 0 to 4, and at most 10 random edges. If a pair (source, target) is generated twice, the method addEdge returns null but the result is simply discarded, so the total number of edges can be less than 10. The weights and the starting vertex are random too.

Then the program calls the algorithm and displays the resulted distances. The utility methods are quite easy to understand.

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 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194

import org.jgrapht.*; import org.jgrapht.graph.*; import java.util.*; /* * Class to represent a vertex in my program * This library only files vertices by contents, not using any kind of ID * thus denying the possibility of changing a vertex after insertion * But I need an ID together with the distance */ class VertexPair { public Double distance; public int vertex; public VertexPair(Double distance, int vertex) { this.distance = distance; this.vertex = vertex; } } public class Dijkstra { public static void main(String[] args) { DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> dijkstraGraph; dijkstraGraph = new DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge>(DefaultWeightedEdge.class); int startVertex = FillGraph(dijkstraGraph); System.out.println(dijkstraGraph); System.out.println(); System.out.println("Printing weights"); PrintWeights(dijkstraGraph); System.out.println(); System.out.println("Showing the minimum possible weight starting from vertex " + startVertex); DijkstraAlgorithm(dijkstraGraph, startVertex); } public static void DijkstraAlgorithm(DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> wg, int s) { /* * Initialization step */ Vector<VertexPair> PriorityQueue = new Vector<VertexPair>(); /* useful structure for computing */ double[] FinalDistances = new double[5]; /* holds the final results to be showed */ for (int i = 0; i < 5; i++) { if (i == s) { FinalDistances[i] = 0.0; /* distance of starting vertex is of course zero */ PriorityQueue.add(new VertexPair(0.0, i)); } else { FinalDistances[i] = Double.POSITIVE_INFINITY; PriorityQueue.add(new VertexPair(Double.POSITIVE_INFINITY, i)); } } /* * Solving step */ while (!PriorityQueue.isEmpty()) { VertexPair vp = getMinElement(PriorityQueue); /* the vertex with minimum distance in the vector */ Set<DefaultWeightedEdge> outgoing = wg.outgoingEdgesOf(vp.vertex); /* all edges coming from the vertex */ for (DefaultWeightedEdge edge : outgoing) { int v = wg.getEdgeTarget(edge); if (getDistanceOf(PriorityQueue, v) > vp.distance + wg.getEdgeWeight(edge)) { setDistanceOf(PriorityQueue, v, vp.distance + wg.getEdgeWeight(edge)); /* changes the entry in the vector */ FinalDistances[v] = vp.distance + wg.getEdgeWeight(edge); /* mirrors the changes here for later */ } } } System.out.println(Arrays.toString(FinalDistances)); } public static int FillGraph(DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> wg) { DefaultWeightedEdge[] edges = new DefaultWeightedEdge[10]; Random generator = new Random(); for (int i = 0; i < 5; i++) { wg.addVertex(i); } for (int i = 0; i < 10; i++) { int source, target; double weight; do { source = generator.nextInt(5); target = generator.nextInt(5); weight = (double)generator.nextInt(20); } while (source == target); edges[i] = wg.addEdge(source, target); if (edges[i] != null) { wg.setEdgeWeight(edges[i], weight); } } return generator.nextInt(5); } public static void PrintWeights(DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> wg) { Set<DefaultWeightedEdge> allEdges = wg.edgeSet(); for (DefaultWeightedEdge edge : allEdges) { System.out.println("w(" + wg.getEdgeSource(edge) + "," + wg.getEdgeTarget(edge) + ") = " + wg.getEdgeWeight(edge)); } } /* * Returns distance of given vertex */ public static double getDistanceOf(Vector<VertexPair> Q, int vertex) { for (VertexPair vp : Q) { if (vp.vertex == vertex) { return vp.distance; } } return Double.NEGATIVE_INFINITY; /* only here for completeness reason, not really useful */ } /* * Sets a new distance for the given vertex */ public static void setDistanceOf(Vector<VertexPair> Q, int vertex, double newDis) { VertexPair toSet = null; /* * Looks for the right entry in the vector */ for (VertexPair vp : Q) { if (vp.vertex == vertex) { toSet = vp; break; } } /* * Changes the distance with newDis */ Q.remove(toSet); toSet.distance = newDis; Q.add(toSet); } /* * Returns minimum distance element in the vector * removing it at the same time */ public static VertexPair getMinElement(Vector<VertexPair> Q) { Double minDis = Double.POSITIVE_INFINITY; VertexPair min = Q.get(0); for (VertexPair element : Q) { if (element.distance < minDis) { minDis = element.distance; min = element; } } Q.remove(min); return min; } }