Presentation

In this presentation, we are not going to solve a specific exercice but we will go thru the Dijkstra Algorithm. Instead of trying to present it, you should definitely take a look to this link. This presentation made on tech.io helps you understand the process of this algorithm and now we gonna code it on a random graph.

Code

In [1]:
import math
import heapq
In [2]:
# Let's create a graph
G = {
    'A' : {'B' : 5, 'C' : 1},
    'B' : {'A' : 5, 'C' : 8, 'E' : 3},
    'C' : {'A' : 1, 'B' : 8, 'D' : 5},
    'D' : {'C' : 5, 'E' : 14, 'G' : 6},
    'E' : {'B' : 3, 'D' : 14, 'F' : 3, 'G' : 21},
    'F' : {'E' : 3},
    'G' : {'D' : 6, 'E' : 21}
}

djikstra.png

Now let's say we start from F to G.

Attention, all weights for paths must be positive or null but not negative !

In [3]:
def dijkstra(graph, source):
    n = len(graph)
    prec = {x : None for x in graph.keys()}
    visited = {x : False for x in graph.keys()}
    dist_to_point = {x: float('inf') for x in graph.keys()}    # set all distances infinite
    dist_to_point[source] = 0                                  # only the source point must have a weight of 0 at start
    heap = [(0, source)]                                       # Queue of all points to visit. Only source as we start from it with a distance of 0
    while heap:                                                # while we have points to visit
        dist_node, node = heapq.heappop(heap)                  # just to extract the point with the smallest distance
        if not visited[node]:
            visited[node] = True                               # mark the point as visited now, it doesn't matter
            for neighbor in graph[node]:
                temp_dist = dist_node + graph[node][neighbor]  # distance to reach the neighbor from the node point
                if temp_dist < dist_to_point[neighbor]:        # if lower, we can save this path
                    dist_to_point[neighbor] = temp_dist
                    prec[neighbor] = node
                    heapq.heappush(heap, (dist_to_point[neighbor], neighbor)) # we add neighbor in the queue to visit
    return dist_to_point, prec
In [4]:
distances, path = dijkstra(G, 'F')
print(path)
{'A': 'B', 'B': 'E', 'C': 'A', 'D': 'E', 'E': 'F', 'F': None, 'G': 'D'}

Now we get the shortest distance from F to any other points and the previous point to take to go on the expected point. We can now reconstruct the complete path

In [5]:
complete_path = ['G']
previous = path['G']
while previous != 'F':
    complete_path.append(previous)
    previous = path[previous]
complete_path.append(previous)
print(" -> ".join(complete_path[::-1]))
F -> E -> D -> G

We can check it tooks the shortest path (23 long). There were longer paths but also a second one with the same distance. It hasn't been chosen because there is more node and when we explored the neighbor of point C, the point D was already set with the same distance. If we validate the path also when distance is equal we have:

In [6]:
def dijkstra_2(graph, source):
    n = len(graph)
    prec = {x : None for x in graph.keys()}
    visited = {x : False for x in graph.keys()}
    dist_to_point = {x: float('inf') for x in graph.keys()}    # set all distances infinite
    dist_to_point[source] = 0             # only the source point must have a weight of 0 at start
    heap = [(0, source)]                  # Queue of all points to visit. Only source as we start from it with a distance of 0
    while heap:                           # while we have points to visit
        dist_node, node = heapq.heappop(heap)   # just to extract the point with the smallest distance
        if not visited[node]:
            visited[node] = True
            for neighbor in graph[node]:
                temp_dist = dist_node + graph[node][neighbor]
                if temp_dist <= dist_to_point[neighbor]:
                    dist_to_point[neighbor] = temp_dist
                    prec[neighbor] = node
                    heapq.heappush(heap, (dist_to_point[neighbor], neighbor))
    return dist_to_point, prec
In [7]:
distances, path = dijkstra_2(G, 'F')
print(path)
{'A': 'B', 'B': 'E', 'C': 'A', 'D': 'C', 'E': 'F', 'F': None, 'G': 'D'}
In [8]:
complete_path = ['G']
previous = path['G']
while previous != 'F':
    complete_path.append(previous)
    previous = path[previous]
complete_path.append(previous)
print(" -> ".join(complete_path[::-1]))
F -> E -> B -> A -> C -> D -> G

We get the 2nd path possible to go to G from F.