Dijkstra's algorithm introduced - With Java and Kotlin examples

1. Introduction

With Dijkstra's algorithm one can find the shortest path (/distance) from a single node to every other node in a graph. A graph is composed by nodes (also called vertices) that are connected by edges. Edges in the graph have certain weights. In Dijkstra's algorithm, it is not allowed for those weights to be negative. Here's an example of such graph. Each node in this graph is a Dutch city, and each edge represents a road from city to city weighted by their distance in kilometers:

If we use Dijkstra's algorithm on that graph, with Amsterdam as our source, we get the shortest distances from Amsterdam to any other city in the graph:

All code examples given in this blog posts are also available on GitHub.

2. Background

Dijkstra's algorithm was conceived by Dutch computer scientist Edsger W. Dijkstra in 1956. Nowadays, Dijkstra is still being used widely. This algorithm is famously used in navigation systems, to find different kind of routes. That could be the shortest in distance, the shortest in time, the most energy efficient, etc. But that's just one of the many applications!

3. How it works

Given the following graphs G with non-negative weighted edges E, nodes V and starting node "Amsterdam" (starting node usually denoted by s).

We also have an initially empty set S. S will contain all nodes whose shortest-path weights are known. In the algorithm we keep on picking nodes from V, that are not contained in S. The node that we pick, we call u. We add u to S. Then, for every edge e that leaves u, we check if the distance of u + weight(e) is smaller than the distance of the node on the other side of the edge. We call this: relaxation. Here you see an example:

But, before relaxing all edges, we must initialize the graph. We do this by setting the distance of s, our source node, to 0, and the distances of any other node initially to ∞. Let's do an example.

Example

Let's use our graph with Dutch cities and their distances. We want to find the shortest paths from Amsterdam to any other city. As stated, we must first initialize our graph by setting the distance of our source node to 0 and all others to ∞, we have an empty set S = {} and a queue with all nodes Q = {Amsterdam, Hilversum, Ede, Utrecht, Tiel, Arnhem}:

Let's start the first iteration: We take node u from Q with the lowest distance, and add it to S. Then we relax all edges leaving u. After doing that, we know that we can reach Hilversum in 34 km and Utrecht in 43 km:

In the graph above you can see that the Amsterdam node now is black, and Hilversum is grey. Black means that the node is in S and grey is the next u (node with the lowest distance, that is not in S). Grey arrows are edges in the shortest paths. We can now repeatedly iterate through the algorithm until all nodes are black, based on the grey edges we can see all shortest paths. Here you see all following iterations:

We are done now. If we remove all edges that are not in the shortest paths, we get the following graph of the shortest paths:

4. Java implementation

For our Java implementation (GitHub), we went for an object-oriented approach. We added three classes:

• NavigationMap: This represents our graph.
• City: This represents a node in our graph.
• Road: This represents a weighted edge in our graph.

Their implementations are as follows:

City

Each city has a name and a list of Road, called roadConnections. What the name represents is pretty straightforward: the name of the city. roadConnections represents all outgoing road to other cities, so basically all leaving edges.

1import java.util.ArrayList;
2import java.util.List;
3
4public class City {
5
6    private final String name;
7    private final List<Road> roadConnections = new ArrayList<>();
8
9    public City(final String name) {
10        this.name = name;
11    }
12
13    public void addRoadConnection(final Road to) {
14        roadConnections.add(to);
15    }
16
17    public List<Road> getRoadConnections() {
18        return roadConnections;
19    }
20
21    public String getName() {
22        return name;
23    }
24}

Road

As already stated, a road represents a leaving edge from one city to another, that 'another city', is called to in the Road class. The weight of the edge is in this case distance and represents the distance to another city in kilometers.

1public class Road {
2
3    final City to;
4    final int distance;
5
6    public Road(final City to, final int distance) {
7        this.to = to;
8        this.distance = distance;
9    }
10
11    public City getTo() {
12        return to;
13    }
14
15    public int getDistance() {
16        return distance;
17    }
18}

NavigationMap

Here's where all the algorithm stuff happens. Recall than NavigationMap is our graph. The nodes in our graph are cities and contained in the list cities. Below that, you see two maps (line 11-12), d and pi. d will store each city with its distance from the source to that city. pi will store for each that, what preceding city it has in the shortest path.

The method printShortestRoutes (line 14-42) executes Dijkstra. It gets one parameter, namely the source node. Between lines 15 and 25 we have our initialization. All distances will initially be set to ∞, except for the source node. The source node gets a distance of 0. On the lines 24-25 we see our sets S and queue Q (implemented using an ArrayList, you can also use a queue data type).

In the lines 27-39 we have our iterations. Each iteration we pick the node from Q, with the lowest distance (line 28) and we relax all its edges (lines 32-38). After finishing, we print all result using prettyPrintShortestRoutes (line 41).

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6public class NavigationMap {
7
8    private static final int INFINITE = Integer.MAX_VALUE;
9
10    private final List<City> cities = new ArrayList<>();
11    private final Map<City, Integer> d = new HashMap<>();
12    private final Map<City, City> pi = new HashMap<>();
13
14    public void printShortestRoutes(final City start) {
15        // Initialize
16        cities.forEach(c -> {
17            d.put(c, INFINITE);
18            pi.put(c, null);
19        });
20
21        // Set distance from start node to 0
22        d.put(start, 0);
23
24        final List<City> S = new ArrayList<>();
25        final List<City> Q = new ArrayList<>(cities);
26
27        while (!Q.isEmpty()) {
28            final City u = extractMin(Q);
29            Q.remove(u);
30            S.add(u);
31
32            for (final Road v : u.getRoadConnections()) {
33                // Relaxation
34                if (d.get(v.to) > d.get(u) + v.distance) {
35                    d.put(v.to, d.get(u) + v.distance);
36                    pi.put(v.to, u);
37                }
38            }
39        }
40
41        prettyPrintShortestRoutes(start);
42    }
43
44    public void addCity(final City city) {
45        cities.add(city);
46    }
47
48    private void prettyPrintShortestRoutes(final City source) {
49        for (final City c : cities) {
50            String road = c.getName();
51            City p = pi.get(c);
52            while (p != null) {
53                road = p.getName() + " -> " + road;
54                p = pi.get(p);
55            }
56
57            System.out.println("Distance from " + source.getName() + " to "
58                    + c.getName() + ": " + d.get(c) + " km");
59            System.out.println("Route: " + road + "\n");
60        }
61    }
62
63    private City extractMin(final List<City> Q) {
64        City min = Q.get(0);
65
66        for (final City c : Q) {
67            if (d.get(c) < d.get(min)) {
68                min = c;
69            }
70        }
71
72        return min;
73    }
74}

Let's test it using data from our example that we used before, the Dutch city map. In the following code we create the graph and pick amsterdam as our source node.

1public class App {
2
3    public static void main(final String[] args) {
4        final City amsterdam = new City("Amsterdam");
5        final City hilversum = new City("Hilversum");
6        final City utrecht = new City("Utrecht");
7        final City ede = new City("Ede");
8        final City tiel = new City("Tiel");
9        final City arnhem = new City("Arnhem");
10
11        amsterdam.addRoadConnection(new Road(hilversum, 34));
12        amsterdam.addRoadConnection(new Road(utrecht, 43));
13        hilversum.addRoadConnection(new Road(ede, 56));
14        hilversum.addRoadConnection(new Road(tiel, 57));
15        hilversum.addRoadConnection(new Road(utrecht, 20));
16        utrecht.addRoadConnection(new Road(hilversum, 20));
17        utrecht.addRoadConnection(new Road(tiel, 50));
18        ede.addRoadConnection(new Road(arnhem, 20));
19        tiel.addRoadConnection(new Road(ede, 37));
20
21        final NavigationMap map = new NavigationMap();
22        map.addCity(amsterdam);
23        map.addCity(hilversum);
24        map.addCity(utrecht);
25        map.addCity(ede);
26        map.addCity(tiel);
27        map.addCity(arnhem);
28
29        map.printShortestRoutes(amsterdam);
30    }
31}

If we run main, we get the following correct output:

1Distance from Amsterdam to Amsterdam: 0 km
2Route: Amsterdam
3
4Distance from Amsterdam to Hilversum: 34 km
5Route: Amsterdam -> Hilversum
6
7Distance from Amsterdam to Utrecht: 43 km
8Route: Amsterdam -> Utrecht
9
10Distance from Amsterdam to Ede: 90 km
11Route: Amsterdam -> Hilversum -> Ede
12
13Distance from Amsterdam to Tiel: 91 km
14Route: Amsterdam -> Hilversum -> Tiel
15
16Distance from Amsterdam to Arnhem: 110 km
17Route: Amsterdam -> Hilversum -> Ede -> Arnhem

5. Kotlin implementation

For out Kotlin implementation (GitHub), we went for a more abstract approach. We have abstracted away from objects and used only integers, arrays and lists. Instead of naming our nodes, we give them consecutive numbers. The main function below, actually creates the same city map graph. But this time, we only have to say that we have 6 nodes, see line 2. We abstracted the cities away by replacing them for numbers: Amsterdam = 0, Hilversum = 1, Ede = 2, Utrecht = 3, Tiel = 4 and Arnhem = 5. Knowing that, we can create weighted edges on line 3-12. On line 4, edges[0][1] = 34, we create an edge from node 0 to node 1 with weight 34. Note that edges is a 2-dimenson. After creating all our edges, we call Dijkstra.

On lines 16-40 we have our Dijkstra implementation. Here, on line 18-19 we have a d and pi array. d will contain for each node, its distance from the source, initially they will have an infinity value (except for the source node, see line 20). pi will contain, for each node, what preceding node it has on its shortest path. Each pi value will initially be null.

On line 22 and 23, we have two lists: S and Q. Q will initially hold all nodes. Whenever we have relaxed all leaving edges from a node (taken from Q), it will be added to S.

We have our iterations in the while loop on line 26. We first pick the node u from Q with the lowest distance. Then, on line 30, we relax all leaving edges from u. After doing that for all nodes, S will contain all nodes and Q will be empty. On line 38 and 39 we print our results.

1fun main() {
2    val nodes = 6
3    val edges: Array<IntArray> = Array(nodes) { IntArray(nodes) { -1 } }
4    edges[0][1] = 34
5    edges[0][3] = 43
6    edges[1][2] = 56
7    edges[1][3] = 20
8    edges[1][4] = 57
9    edges[2][5] = 20
10    edges[3][1] = 20
11    edges[3][4] = 50
12    edges[4][2] = 37
13    dijkstra(0, edges, nodes)
14}
15
16fun dijkstra(source: Int, edges: Array<IntArray>, nodes: Int) {
17    // Initialize single source
18    val d = IntArray(nodes) { Integer.MAX_VALUE }
19    val pi = IntArray(nodes) { -1 }
20    d[source] = 0
21
22    val S: MutableList<Int> = ArrayList()
23    val Q: MutableList<Int> = (0 until nodes).toMutableList()
24
25    // Iterations
26    while (Q.isNotEmpty()) {
27        val u: Int = extractMin(Q, d)
28        S.add(u)
29
30        edges[u].forEachIndexed { v, vd ->
31            if (vd != -1 && d[v] > d[u] + vd) {
32                d[v] = d[u] + vd
33                pi[v] = u
34            }
35        }
36    }
37
38    println("d: ${d.contentToString()}")
39    println("pi: ${pi.contentToString()}")
40}
41
42fun extractMin(Q: MutableList<Int>, d: IntArray): Int {
43    var minNode = Q[0]
44    var minDistance: Int = d[0]
45
46    Q.forEach {
47        if (d[it] < minDistance) {
48            minNode = it
49            minDistance = d[it]
50        }
51    }
52
53    Q.remove(minNode)
54    return minNode
55}

Running main, gives us the following output:

1d: [0, 34, 90, 43, 91, 110]
2pi: [-1, 0, 1, 0, 1, 2]

Let's compare that output to the graph we showed before:

Recall that Amsterdam now is node 0. If we look at d[0], the distance to Amsterdam, we see the value 0. And pi[0] = -1, meaning that Amsterdam has no predecessor, which is correct, since it's our source node. If you compare the other nodes, you'll see that the result is the same.

6. Efficiency

The running time of Dijkstra's algorithm is depending on its implementation, for example the way you implement extractMin or what kind of data structures you use. In its worst-case scenario, Dijkstra costs O(|E| + |V| log |V|).

This concludes the short introduction to Dijkstra's algorithm. If you want to learn more about this algorithm, we recommend you dive deeper into the proof and correctness of the algorithm. That way you'll understand the algorithm even more. All code provided in this blog post are available on GitHub.