Dijkstra’s Algorithm, Visualized

The purpose of Dijkstra’s algorithm is to locate the shortest path from one vertex to any connected vertex in a weighted graph. This algorithm works for both directed and undirected graphs, with some minor modifications. Below is the graph we will be traversing.

First, some preprocessing:

1. Create a table containing all vertices in the graph.
2. Create columns to store the shortest path to each vertex, as well as the vertex from which this path originates from.
3. Populate all but the starting vertex’s shortest path cells with values of infinity. Set the starting vertex’s shortest path value to 0, as it is the starting vertex.
4. Initialize 2 lists, one for visited and another for unvisited vertices. Populate the unvisited list with all graph vertices. You should have something that looks like the below figure.

Fig. 1

With the pre-processing complete, we can start Dijkstra’s algorithm.

1. Begin by visiting the vertex in the unvisited list with the smallest known distance from the start vertex. In this case, this is vertex A.
2. For this vertex, visit all unvisited neighbors. In this graph, these are vertices B and C.
3. Find the distance from the starting vertex to each neighbor. This is done by adding the distance of the previous vertex to the distance to the neighbor. For vertex B, this is 0 + 3. For vertex C, this is 0 + 1.
4. If these new distances are less than the recorded “shortest distance” for the neighbors, replace with the new and shorter distance, as well as inserting the previous vertex (A in this case) into the previous vertex column.
5. Now that A has been visited, remove it from the unvisited list and place it in the visited list. The table should now look like fig 2.

Fig. 2

1. The algorithm begins anew. Once more, visit the unvisited vertex with the lowest distance. In this case, that vertex is C.
2. Visit all of C’s unvisited neighbors. These neighbors are B, E, and F.
3. Find the distance from the starting vertex (A) to each of these neighbors.

• B: 1 + 7 = 8
• E: 1 + 9 = 10
• F: 1 + 12 = 13

4. Compare these new distances to the shortest distances in the table.

• B: This calculated distance is 8, which is greater than the previous shortest distance of 3. We will not replace the distance.
• E: This calculated distance is 10, which is less than the previous shortest distance of infinity. Replace infinity with 10 and update the previous vertex to be the current vertex, C.
• F: This calculated distance is 13, less than the recorded distance of infinity. Replace with 13 and update the previous vertex to C.

5. C is now visited. Move it from the unvisited to visited list. Refer to fig 3.

Fig. 3

1. Repeat the algorithm again. This time we will select vertex B, as it has the lowest distance amongst the unvisited vertices.
2. Visit B’s unvisited neighbors and calculate their distances through B. In this case, the only neighbor is D. D’s distance is B’s distance plus the distance between B and D. 3 + 6 = 9.
3. D’s shortest distance is recorded as infinity, which is greater than 9. Replace it with 9 and update the previous vertex to B.
4. All of B’s univisited neighbors have been processed. Move B to the visited list. The table should now look like fig 4.

Fig. 4

1. Again, repeat the algorithm. Of the remaining unvisited vertices, D has the lowest distance. Begin from D.
2. D’s only neighbor (and also unvisited vertex) is F. Calculate the distance from A to F, through D.
3. A →F = D’s shortest distance + distance to F = 9 + 2 = 11
4. F’s distance is 11. This is shorter than the recorded distance of 13 in the table. Replace 13 with 11 and update the previous vertex of C to D.
5. All of D’s neighbors are visited. Mark D as visited. The table should look like fig 5.

Fig. 5

1. Of the remaining unvisited vertices, E has the shortest distance. Select it.
2. E’s neighbors are D. D has already been visited so it is skipped.
3. E is now visited. Move it to the visited list. The table should not have changed from fig 5.
4. The final unvisited vertex is F. Select it and check its neighbors.
5. Vertex F has no neighbors. Mark it as visited.
6. There are no remaining unvisited vertices. The algorithm is complete. The completed table should look like fig 6.

Fig. 6

Find the Shortest Path

The resulting table can now be used to find the shortest distance between A and any vertex. One way to find this path is to work backwards. Let’s try to find the shortest path between A and D.

1. Begin by finding D in the table. Its previous vertex is B.
2. Now look at the previous vertex of B. It is A.
3. A is the starting vertex so we stop here. If we reverse the order of traversal, we see we have found the path of A →B →D. This is the shortest path.
4. To confirm, we can also see that the added distances of this path are 3 + 6, which is also the shortest distance of D as recorded in the table.

In conclusion, we have found that the shortest path between A and D is A →B →D, with a total weight of 9.

Python Implementation

The implementation of Dijkstra’s algorithm in Python is below. Our input will be a dictionary with vertices as keys and neighboring vertices arranged within an array. Index 0 is the vertex, index 1 is the weight. The list of neighbors is the key’s value.

Writing the code:

First, create an empty dictionary to act as our table. Initialize this dictionary with vertices as keys and lists as values.

For each array, index 0 will store the shortest distance and index 1 will store the previous vertex. Initialize table[starting_node] with a distance of 0. Set all other distances to infinity and all previous vertices to null or empty strings.

def build_table(graph, start):
    table = {}
        for vertex in graph:
            if vertex == start:
                table[vertex] = [0, ""]
            else:
                table[vertex] = [math.inf, ""]

Initialize an empty visited array and unvisited array populated with all vertices in the table. Also create a pointer for the current node and set it to the starting vertex. Create another pointer for the current node’s neighbors, which should be a list of vertices and their weights.

def build_table(graph, start):
    table = {}
    for vertex in graph:
        if vertex == start:
            table[vertex] = [0, ""]
        else:
            table[vertex] = [math.inf, ""]
    visited = []
    unvisited = [key for key in table]
    current = start
    neighbors = graph[current]

We want this algorithm to loop until there are no more vertices to visit. Write a while loop to accomplish this. Within the while loop, we begin to write our algorithm logic. First, we need to perform some calculations for each of the current node’s neighbors.

For each neighbor, ensure it has not yet been visited. Skip it if it has been visited. Otherwise, calculate the total distance between the current node’s shortest path to the start and the neighbor’s weight.

    ...
    neighbors = graph[current]
    while len(unvisited) > 0:
        for neighbor in neighbors:
            if neighbor[0] not in visited:
                distance = neighbor[1]
                total_distance = table[current][0] + distance

If this total distance is less than the neighbor’s recorded shortest distance in the table, replace the distance with the new total distance. Also replace the previous vertex with the current vertex.

    ...
    if neighbor[0] not in visited:
        distance = neighbor[1]
        total_distance = table[current][0] + distance
        
        if total_distance < table[neighbor[0]][0]:
            table[neighbor[0]][0] = total_distance
            table[neighbor[0]][1] = current

Repeat for all neighbors. When complete, mark the current node as visited and remove it from the unvisited array. Now we need to calculate which vertex to set as our next current node. Your code should look like the below.

def build_table(graph, start):
    table = {}
    for vertex in graph:
        if vertex == start:
            table[vertex] = [0, ""]
        else:
            table[vertex] = [math.inf, ""]
    visited = []
    unvisited = [key for key in table]
    current = start
    neighbors = graph[current]
    while len(unvisited) > 0:
        for neighbor in neighbors:
        if neighbor[0] not in visited:
            distance = neighbor[1]
            total_distance = table[current][0] + distance
        
            if total_distance < table[neighbor[0]][0]:
                table[neighbor[0]][0] = total_distance
                table[neighbor[0]][1] = current
        
        visited.append(current)
        unvisited.remove(current)

Initialize a variable to store the lowest distance and set it to an arbitrarily large value. For each vertex in the unvisited array, if the vertex’s value is less than the min_distance value AND the vertex’s value is not 0 (which would be the starting node), set the min_distance to that vertex’s value.

...
unvisited.remove(current)
min_distance = math.inf
for vertex in unvisited:
    if table[vertex][0] < min_distance and table[vertex][0] != 0:
        min_distance = table[vertex][0]

We have now found the smallest unvisited vertex. Use the value to set the current vertex pointer to the smallest unvisited vertex and find the neighbors of the new current vertex.

...
unvisited.remove(current)
min_distance = math.inf
for vertex in unvisited:
    if table[vertex][0] < min_distance and table[vertex][0] != 0:
        min_distance = table[vertex][0]
for vertex in table:
    if table[vertex][0] == min_distance:
        current = vertex
neighbors = graph[current]

The while loop repeats until no vertices remain unvisited. At this point, the table has been fully updated. Return table outside the while loop. It’s probably not a good idea to skip this step.

The code to trace the shortest path between the starting node and any other node is below. It is relatively simplistic, so I’ll refrain from explaining it.

def find_shortest_path(table, start, end):
    path = []
    current = end
    while table[current][0] != 0:
        path.append(current)
        current = table[current][1]
    path.append(start)
    path.reverse()
    
    return path

Find all the code on Github here.