Unlocking the Steps of Dijkstra: A Step-by-Step Guide + Python code (part 1)

Have you ever wondered how a mapping platform like Google Maps is able to return the shortest routes to your destination? Or how do automated vehicles find the best routes to avoid obstacles?

The secret lies in the power of graph search algorithms. A graph search algorithm is a method used in mathematics to traverse a graph and understand the relationships between its nodes. A graph is a data structure that consists of nodes and edges, where each edge may have a weight. An illustration of a graph with nodes and edges is shown in Figure 1.

Figure 1. A graph consists of several nodes and edges

If the concept of a graph is still too abstract, we can imagine the graph as a road network. This network consists of cities and connecting roads that represent nodes and edges. The length of the road between cities can be assumed as the weight of the edges. See Figure 2 to see the illustration.

Figure 2. A road network connecting Semarang city and the surrounding cities

Given the task of finding the shortest path between two nodes, we need a search algorithm. In this article, we will learn how to solve the shortest path problem with two search algorithms: Dijkstra (part 1) and A* (part 2). I guarantee the reader of this article can solve the shortest path problem without fancy mathematical skills.

Dijkstra

In a nutshell, the Dijkstra algorithm starts at a specified starting node (in Figure 3, node “A” which is represented by the yellow node) and then iteratively selects the unvisited node with the lowest accumulated cost, which is defined as the sum of the edge weights along the path from the starting node to the current node. The algorithm continues this process until it reaches the goal node (in the example, node “H” which is represented by the green node).

Figure 3. Example of graph

To solve this example, we will take several steps:

Step 1 -> | A
Explanation: Start with initial node A

Step 2 -> A | B(A,1) C(A,2)
Explanation: Find the unvisited neighbors of node A, which are B and C, then put them to the right of “|”. The values inside ( ) are respectively the previous node and the cost to the neighbor node from initial node A. Put the previous node, which is A, to the left of “|”.

Figure 4. Illustration of A | B(A,1) C(A,2)

Step 3 -> A B | C(A,2) D(B,3)
Explanation: Always start with the node from the right of “|” that has the lowest cost from initial node A, which is B. Find the unvisited neighbors of node B, which is D, then put it to the right of “|”. Put the previous node, which is B, to the left of “|”.

Figure 5. Illustration of A B | C(A,2) D(B,3)

Step 4 -> A B C | D(B,3) E(C,3) F(C,4)
Explanation: Always start with the node from the right of “|” that has the lowest cost from initial node A, which is C. Find the unvisited neighbors of node C, which are E and F, then put it to the right of “|”. We don’t choose D as the neighbor of C because we already visit D as the neighbor of B. Put the previous node, which is B, to the left of “|”.

Figure 6. Illustration of A B C | D(B,3) E(C,3) F(C,4)

Step 5 -> A B C D | E(C,3) F(C,4) G(D,4)
Explanation: Always start with the node from the right of “|” that has the lowest cost from initial node A. In this case, both node D and node E have the same cost from the initial node A, so we can randomly pick one of them. Find the unvisited neighbors of node D, which is G, then put it to the right of “|”. Put the previous node, which is D, to the left of “|”.

Figure 7. Illustration of A B C D | E(C,3) F(C,4) G(D,4)

Step 6 -> A B C D E | F(C,4) G(D,4) H(E,6)
Explanation: Always start with the node from the right of “|” that has the lowest cost from initial node A, which is E. Find the unvisited neighbors of node E, which is H, then put it to the right of “|”. Put the previous node, which is E, to the left of “|”. In this situation, we have reached node H, but, we still have two uncovered nodes, which are F and G. Continue the step until we have no other nodes left.

Figure 8. Illustration of A B C D E | F(C,4) G(D,4) H(E,6)

Step 7 -> A B C D E F |G(D,4) H(F,5)
Explanation: Always start with the node from the right of “|” that has the lowest cost from initial node A. In this case, both node F and node G has the same cost from the initial node A, so we can randomly pick one of them. Find the unvisited neighbors of node F, which is H, then put it to the right of “|”. Put the previous node, which is F, to the left of “|”. In this situation, we have reached node H from two different nodes. Remove node H(E,6) because it has a higher cost compared to H(F,5). As we still have the last uncovered node, which is G, continue the step until we have no other nodes left.

Figure 9. Illustration of A B C D E F |G(D,4) H(E,6) H(F,5)

Step 8 -> A B C D E F G | H(F,5)
Explanation: Always start with the node from the right of “|” that has the lowest cost from initial node A. Find the neighbors of node G, which is H, then put it to the right of “|”. Put the previous node, which is G, to the left of “|”. In this situation, we have reached node H and we have no uncovered node left. Choose the pair of nodes that has the lowest cost, which is H(F,5).

Figure 10. Illustration of A B C D E F G | H(G,7) H(E,6) H(F,5)

Step 9 -> Choose the shortest path
As we know that the shortest path comes from node H(F,5), we can trace back the previous node until we reach the initial node A. The shortest path is A -> C -> F -> H.

Figure 11. The shortest path

To implement the Dijkstra algorithm in Python, we first need to define the graph. We can use a graph.csv file, shown below, to save the graph representation in Figure 3. Each row shows one edge with the following information: a starting node, a neighbor node, and the cost to travel from starting node to the neighbor node.

A,B,1
A,C,2
B,D,2
C,D,1
C,E,1
C,F,2
D,G,1
F,E,1
F,H,1
E,G,1
E,H,3
G,H,3

Create a function read_graph_from_csv() to read graph.csv and convert it to the graph representation. If we run the code below, we will get the representation of the graph as follows:

import csv

def read_graph_from_csv(filename):
    graph = {}
    with open(filename) as f:
        reader = csv.reader(f)
        for u, v, w in reader:
            if u not in graph:
                graph[u] = []
            if v not in graph:
                graph[v] = []
            graph[u].append((v, int(w)))
            graph[v].append((u, int(w)))
    return graph

graph = read_graph_from_csv('graph.csv')
graph

Output:
{'A': [('B', 1), ('C', 2)],
 'B': [('A', 1), ('D', 2)],
 'C': [('A', 2), ('D', 1), ('E', 1), ('F', 2)],
 'D': [('B', 2), ('C', 1), ('G', 1)],
 'E': [('C', 1), ('F', 1), ('G', 1), ('H', 3)],
 'F': [('C', 2), ('E', 1), ('H', 1)],
 'G': [('D', 1), ('E', 1), ('H', 3)],
 'H': [('F', 1), ('E', 3), ('G', 3)]}

Create a function dijkstra() with the input of the graph, the starting node, and the goal node. This function will produce the travel distances with the nodes it visits.

def dijkstra(graph, start, goal):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    unvisited = set(graph.keys())
    previous = {node: None for node in graph}
    current = start
    while unvisited:
        for neighbor, weight in graph[current]:
            if neighbor in unvisited:
                new_dist = distances[current] + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    previous[neighbor] = current
        unvisited.remove(current)
        if current == goal:
            break
        candidates = {node: distances[node] for node in unvisited}
        current = min(candidates, key=candidates.get)
    return distances, previous

def shortest_path(previous, start, goal):
    node = goal
    path = [node]
    while node != start:
        node = previous[node]
        path.append(node)
    path.reverse()
    return path

graph = read_graph_from_csv('graph.csv')
start = 'A'
goal = 'H'
distances, previous = dijkstra(graph, start, goal)

path = shortest_path(previous, start, goal)
print("Shortest path from node {} to node {}: {}".format(start, goal, path))

Output:
Shortest path from node A to node H: ['A', 'C', 'F', 'H']

If you have read this sentence, it means that you have successfully used Dijkstra’s algorithm to find the shortest path! Congratulations.