« Blogs # Dijkstra's algorithm introduced - With Java and Kotlin examples

2020-11-03 15:40:34.664378

## 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 nonnegative 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 lowest distance, that is not in `S`). Grey arrows are edges in 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 shortest paths, we get the following graph of 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.

``````
import java.util.ArrayList;
import java.util.List;

public class City {

private final String name;
private final List<Road> roadConnections = new ArrayList<>();

public City(final String name) {
this.name = name;
}

public void addRoadConnection(final Road to) {
roadConnections.add(to);
}

public List<Road> getRoadConnections() {
return roadConnections;
}

public String getName() {
return name;
}
}
```
```
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.

``````
public class Road {

final City to;
final int distance;

public Road(final City to, final int distance) {
this.to = to;
this.distance = distance;
}

public City getTo() {
return to;
}

public int getDistance() {
return distance;
}
}
```
```
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).

``````
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NavigationMap {

private static final int INFINITE = Integer.MAX_VALUE;

private final List<City> cities = new ArrayList<>();
private final Map<City, Integer> d = new HashMap<>();
private final Map<City, City> pi = new HashMap<>();

public void printShortestRoutes(final City start) {
// Initialize
cities.forEach(c -> {
d.put(c, INFINITE);
pi.put(c, null);
});

// Set distance from start node to 0
d.put(start, 0);

final List<City> S = new ArrayList<>();
final List<City> Q = new ArrayList<>(cities);

while (!Q.isEmpty()) {
final City u = extractMin(Q);
Q.remove(u);
S.add(u);

for (final Road v : u.getRoadConnections()) {
// Relaxation
if (d.get(v.to) > d.get(u) + v.distance) {
d.put(v.to, d.get(u) + v.distance);
pi.put(v.to, u);
}
}
}

prettyPrintShortestRoutes(start);
}

public void addCity(final City city) {
cities.add(city);
}

private void prettyPrintShortestRoutes(final City source) {
for (final City c : cities) {
String road = c.getName();
City p = pi.get(c);
while (p != null) {
road = p.getName() + " -> " + road;
p = pi.get(p);
}

System.out.println("Distance from " + source.getName() + " to "
+ c.getName() + ": " + d.get(c) + " km");
System.out.println("Route: " + road + "\n");
}
}

private City extractMin(final List<City> Q) {
City min = Q.get(0);

for (final City c : Q) {
if (d.get(c) < d.get(min)) {
min = c;
}
}

return min;
}
}
```
```

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.

``````
public class App {

public static void main(final String[] args) {
final City amsterdam = new City("Amsterdam");
final City hilversum = new City("Hilversum");
final City utrecht = new City("Utrecht");
final City ede = new City("Ede");
final City tiel = new City("Tiel");
final City arnhem = new City("Arnhem");

amsterdam.addRoadConnection(new Road(hilversum, 34));
amsterdam.addRoadConnection(new Road(utrecht, 43));
hilversum.addRoadConnection(new Road(ede, 56));
hilversum.addRoadConnection(new Road(tiel, 57));
hilversum.addRoadConnection(new Road(utrecht, 20));
utrecht.addRoadConnection(new Road(hilversum, 20));
utrecht.addRoadConnection(new Road(tiel, 50));
ede.addRoadConnection(new Road(arnhem, 20));
tiel.addRoadConnection(new Road(ede, 37));

final NavigationMap map = new NavigationMap();
map.addCity(amsterdam);
map.addCity(hilversum);
map.addCity(utrecht);
map.addCity(ede);
map.addCity(tiel);
map.addCity(arnhem);

map.printShortestRoutes(amsterdam);
}
}
```
```

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

``````
Distance from Amsterdam to Amsterdam: 0 km
Route: Amsterdam

Distance from Amsterdam to Hilversum: 34 km
Route: Amsterdam -> Hilversum

Distance from Amsterdam to Utrecht: 43 km
Route: Amsterdam -> Utrecht

Distance from Amsterdam to Ede: 90 km
Route: Amsterdam -> Hilversum -> Ede

Distance from Amsterdam to Tiel: 91 km
Route: Amsterdam -> Hilversum -> Tiel

Distance from Amsterdam to Arnhem: 110 km
Route: 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 = 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.

``````
fun main() {
val nodes = 6
val edges: Array<IntArray> = Array(nodes) { IntArray(nodes) { -1 } }
edges = 34
edges = 43
edges = 56
edges = 20
edges = 57
edges = 20
edges = 20
edges = 50
edges = 37
dijkstra(0, edges, nodes)
}

fun dijkstra(source: Int, edges: Array<IntArray>, nodes: Int) {
// Initialize single source
val d = IntArray(nodes) { Integer.MAX_VALUE }
val pi = IntArray(nodes) { -1 }
d[source] = 0

val S: MutableList<Int> = ArrayList()
val Q: MutableList<Int> = (0 until nodes).toMutableList()

// Iterations
while (Q.isNotEmpty()) {
val u: Int = extractMin(Q, d)
S.add(u)

edges[u].forEachIndexed { v, vd ->
if (vd != -1 && d[v] > d[u] + vd) {
d[v] = d[u] + vd
pi[v] = u
}
}
}

println("d: \${d.contentToString()}")
println("pi: \${pi.contentToString()}")
}

fun extractMin(Q: MutableList<Int>, d: IntArray): Int {
var minNode = Q
var minDistance: Int = d

Q.forEach {
if (d[it] < minDistance) {
minNode = it
minDistance = d[it]
}
}

Q.remove(minNode)
return minNode
}
```
```

Running `main`, gives us the following output:

``````
d: [0, 34, 90, 43, 91, 110]
pi: [-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`, the distance to Amsterdam, we see the value `0`. And `pi = -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.