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.
* 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
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("Showing the minimum possible weight starting from vertex " + 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; /* 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));
FinalDistances[i] = Double.POSITIVE_INFINITY;
PriorityQueue.add(new VertexPair(Double.POSITIVE_INFINITY, i));
* Solving step
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 */
public static int FillGraph(DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> wg)
DefaultWeightedEdge edges = new DefaultWeightedEdge;
Random generator = new Random();
for (int i = 0; i < 5; i++)
for (int i = 0; i < 10; i++)
int source, target;
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)
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 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;
* Changes the distance with newDis
toSet.distance = newDis;
* 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;