in Graph

Exploring Dijkstra’s shortest path algorithm

Several graph algorithms can help reveal hidden patterns in connected data. These algorithms can be classified into several categories such as approximations (e.g clustering), assortativity (e,g average neighbour degree), communities (e.g K-Clique) and centrality (e.g shortest path). In this blog, we will be looking at one of the most popular shortest path algorithms known as the Dijkstra’s algorithm. Exploring an example table and code implementation for this algorithm. Shortest path algorithm can be relevant in a traffic network situation a user desires to discover the fastest way to move from a source to a destination. It is an iterative algorithm that provides us with the shortest path from an origin node to all other nodes in the graph. This algorithm can work in weighted and unweighted graph scenarios. 

Above is an unweighted graph with ten vertices. In this scenario, the shortest path from one node to another is the fewest number of nodes that will be required to move from the source to the destination. 

Using the NetworkX library in Python, I was able to check the shortest path from node 1 to 4 and it reveals  [1,2,4] as the fastest route. You might be wondering why [1.5.4] was not considered as that is also a two-node movement?

print(nx.dijkstra_path(G,1,4))

[1, 2, 4]

I am now going to check the shortest path from nodes 1 to 8. As you can see below, the route [1,7,8] was chosen when [1,10,8] also contains the same number of paths. The path [1,7,8] has lower values when compared to [1.10.8]

print(nx.dijkstra_path(G,1,8))

[1, 7, 8]

After adding weights to all edges, the shortest path from nodes [1] to [8] was rechecked and route [1, 6, 7, 8] was revealed. This was done with both the Dijkstra and Johnson’s algorithm. 

paths = nx.johnson(G, weight='weight') #Johnson's Algorithm

paths[1][8]

[1, 6, 7, 8]

print(nx.dijkstra_path(G,1,8))

[1, 6, 7, 8]

We can also use the Dijkstra’s algorithm to obtain the shortest weighted paths and return dictionaries of predecessors for each node and distance for each node from the source node. In this example, we adopt node [2] as our source and populate a dictionary of the nodes on the path from the source to the destination. It indicates that from node [2] to node [8] there are three paths which will travel from either node 7, 10 or 9.

pred, dist = nx.dijkstra_predecessor_and_distance(G, 2)

sorted(pred.items())

sorted(dist.items())

Path Length

NetworkX also allows you to determine the path length from a source to a destination node. Helping you know the count of the shortest path length. The first example below, from node [1] to [4], reveals the fastest length in weights. While the second example expresses a length of 5.7 in weight as the shortest distance from nodes [4] to [9]. 

length = nx.single_source_dijkstra_path_length(G, 1)

length[4]

length = nx.single_source_dijkstra_path_length(G, 4)

length[9]

5.7

Non-NetworkX implementation of the Dijkstra’s algorithm

We will now look at the Python implementation of Dijkstra’s algorithm without the NetworkX library. 

As a reminder, Djikstra’s is a path-finding algorithm, common in routing and navigation applications. The weight of edges determines the shortest path.  The weights can represent cost, time, distance, rate of flow or frequency.

The first step is to create a Graph and initialise the edge and weight dictionaries. When defining the add_edge function, provisions are made to capture an out-degree and an in-degree weight. The from_node and to_node arguments compute the bidirectional weight to determine the shortest path. For example, a path [A, B] with weight 2, and [B, A] with weight 1, will lead to a combined weight of 3 from A to B. 

from collections import defaultdict


class Graph():
    def __init__(self):
        """
        self.edges is a dict of every possible next nodes
        e.g. {'Z': ['A', 'B', 'C',], ...}
        self.weights contains the weights between two nodes,
        ...the two nodes serving as the tuple
        e.g. {('Z', 'A'): 11, ('Z', 'C'): 2.4, ...}
        """
        self.edges = defaultdict(list)
        self.weights = {}
    
    def add_edge(self, from_node, to_node, weight):
        # connecting nodes from both sides
        self.edges[from_node].append(to_node)
        self.edges[to_node].append(from_node)
        # catering for the source and destination nodes
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight
        # combining the indegree and outdegree weights were possible

The next step is to create edges between nodes and assign specific weights to these connections. These assigned weights will determine the shortest path.

graph = Graph()

#nodes are created as edge connections and weights are determined
edges = [
    ('Z', 'A', 11),
    ('Z', 'B', 2.8),
    ('Z', 'C', 2.4),
    ('A', 'B', 3.9),
    ('A', 'D', 14),
    ('A', 'F', 1),
    ('B', 'D', 4),
    ('B', 'H', 5),
    ('C', 'L', 2),
    ('D', 'F', 1),
    ('F', 'H', 3),
    ('G', 'H', 2),
    ('G', 'Y', 2),
    ('I', 'J', 60),
    ('I', 'K', 41),
    ('I', 'L', 48),
    ('J', 'L', 12),
    ('K', 'Y', 50),
]
for edge in edges:
    graph.add_edge(*edge)

The next step is to utilise the Dijkstra algorithm to find the shortest path. Beginning with the current_node and adding the weight of that node to the next one. The shortest weight equates to the shortest path in this case.

def dijsktra(graph, initial, end):
    # the shortest paths is a dict of nodes
    # whose value is a tuple of (previous node, weight)
    shortest_paths = {initial: (None, 0)}
    current_node = initial
    visited = set()
    
    while current_node != end:
        visited.add(current_node)
        destinations = graph.edges[current_node]
        weight_to_current_node = shortest_paths[current_node][1]

        for next_node in destinations:
            weight = graph.weights[(current_node, next_node)] + weight_to_current_node
            if next_node not in shortest_paths:
                shortest_paths[next_node] = (current_node, weight)
            else:
                current_shortest_weight = shortest_paths[next_node][1]
                if current_shortest_weight > weight:
                    shortest_paths[next_node] = (current_node, weight)
        
        next_destinations = {node: shortest_paths[node] for node in shortest_paths if node not in visited}
        if not next_destinations:
            return "Route Not Possible"
        # the next node is the destination with the lowest weight
        current_node = min(next_destinations, key=lambda k: next_destinations[k][1])
    
    # determing the shortest path
    path = []
    while current_node is not None:
        path.append(current_node)
        next_node = shortest_paths[current_node][0]
        current_node = next_node
    # Reverse path
    path = path[::-1]
    return path

A quick test was run to determine the shortest path from [Z] to [D]. It predicted [Z,B,D] as the shortest path. This is correct as the weight for [Z, B, D] is 6.8 and that of [Z, A, D] is 25. 

For the second example, the goal was to discover the shortest path from A to H. The result generated was correct by identifying [A, F, H] as the shortest path with a total weight of 4 when compared to a longer route of [A, B, H] with a weight of 8.9

dijsktra(graph, 'Z', 'D')
['Z', 'B', 'D']

dijsktra(graph, 'A', 'H')
['A', 'F', 'H']

Write a Comment

Comment