Dijkstra Intro | Shortest Path in a Weighted Graph

The Problem

Given a weighted graph, what is fastest way to compute the shortest path from a node to every other node. What we mean by weighted graph is that every edge is now assigned a weight that and our distance increases by the weight instead of 1. This problem means that our previous graph theory algorithms such as BFS don't work anymore as they are designed for unweighted graphs. The previous algorithms assumed each edge was equal so only need to visit each node once. That no longer works as the first time we visit a node does not guarantee minimum distance and we may need to revisit the node if we find a shorter path. Is there a way to update them to account for weighted graphs in general.

The Shortest-Path Faster Algorithm

The Shortest-Path Faster Algorithm abbreviated to SPFA can be thought of as a BFS variant. Instead of checking whether or not the neighbour node has been visited we instead see if we can imrpove our distance by checking the neighbor nodes and if it possible to update to a smaller distance and push the node into our queue. If it is greater then we want to update the node's distance since we have found a shorter path and push the node into our queue. This algorithm runs in worst case O(n * m) where n is the number of nodes in our graph and m is the number of edges. Here is some example code for how this version would work, note that this code has some pseudo-code and is only meant to give you an idea of what an implementation would look like.

from collections import deque

def spfa(root):
    queue = deque([root])
    distance = {}
    # initialize each nodes' distance value to infinity
    while len(queue) > 0:
        node = queue.popleft()
        # can vary depending on implementation how neighbor nodes are retrieved, adjjust based on your implementation
        for neighbor in get_neighbors(node):
            if distance.get(neighbor) <= distance.get(node) + neighbor.weight:
                continue
            queue.append(neighbor)
            distance.get(neighbor) = distance.get(node) + neighbor.weight

This algorithm works for smaller graphs and is easy to implement, so if you are in a rush and can afford to have a less efficient algorithm, you may want to use SPFA. Can we do better though?

Dijkstra's algorithm

The big improvement that Dijkstra makes is the use of a Priority Queue to maintain the node that is closest to our source node. That way the first time we visit a node we now that it is the shortest distance from our source node. The time complexity is therefore similar to BFS as we only ever consider each node and therefore each edge once except for maintaining the queue. Each time we insert a node or pop a node from the queue it takes time logarithmic to the size of the queue. Therefore, our final time complexity is O(nlog(e)) as maintaining the edges in the queue takes logarithmic time. Here is some code to get you started on an implementation.

import heapq

def dijkstra(root):
    queue = [root]
    distance = {}
    # initialize each nodes' distance value to infinity
    while len(queue) > 0:
        node = queue.get()
        # can vary depending on implementation how neighbor nodes are retrieved, adjjust based on your implementation
        for neighbor in get_neighbors(node):
            if distance.get(neighbor) <= distance.get(node) + neighbor.weight:
                continue
            heapq.heappush(queue, neighbor)
            distance.get(neighbor) = distance.get(node) + neighbor.weight

Optimizations

There are some optimizations we can do for dijkstra, that can improve the time complexity.

The first optimization is that we can check our Priority Queue and if the distance in our Priority Queue is greater than the distance that is currrently in the array we pop it out and skip to the next iteration of the loop. Here is some code that shows this idea.

from collections import deque

def dijkstra(root):
    # need to make a custom comparator class for the Priority Queue
    queue = PriorityQueue([root])
    distance = {}
    # initialize each nodes' distance value to infinity
    while len(queue) > 0:
        node = queue.get()
        if node.distance > distance.get(node):
            continue
        # can vary depending on implementation how neighbor nodes are retrieved, adjjust based on your implementation
        for neighbor in get_neighbors(node):
            if distance.get(neighbor) <= distance.get(node) + neighbor.weight:
                continue
            queue.insert(neighbor)
            distance.get(neighbor) = distance.get(node) + neighbor.weight

The other optimization is to terminate the search as soon as you reach a destination node. This is if you are using Dijkstra specifically to find the distance only between 2 nodes. If this is the case you can terminate the search early and exit the loop as soon as you reach the destination node.