Dijkstra's Algorithm

Whether you are using a GPS to drive to a new city or routing data packets across the internet, finding the optimal path is crucial. Dijkstra's Algorithm is one of the most famous and reliable methods for finding the shortest path from a starting node to a target node in a graph with weighted edges.

The Pathfinder Principle

The algorithm systematically evaluates paths and "relaxes" the distances as it finds shortcuts. Here is the logic:

• Initialize the distance to the starting node as 0 and all other nodes as infinity.
• Maintain a Priority Queue to always pop the node with the smallest cumulative distance.
• For the current node, look at all its neighbors and calculate the distance to reach them via the current node.
• If this new distance is shorter than the previously recorded distance for that neighbor, update it (this is called edge relaxation) and remember the current node as its "previous" step.
• If the algorithm reaches the target node, it can stop early.
• Finally, backtrack from the target node using the "previous" steps to reconstruct the exact shortest path.

Algorithm Walkthrough

Below is the Python implementation used in our animation engine. Notice the use of previous_nodes to leave a trail of breadcrumbs so we can reconstruct the path at the end.

def dijkstra_shortest_path(start_node, target_node):
    import math

    distances = {}
    previous_nodes = {}
    pq = [(0, start_node)]

    distances[start_node] = 0

    visit(
        start_node, f"Launching Dijkstra pathfinding from {start_node} to {target_node}"
    )

    while len(pq) > 0:
        # Sort to simulate a Priority Queue (always pop the smallest distance)
        pq.sort(key=lambda x: x[0])
        current_distance, current_node = pq.pop(0)

        # Skip if we already found a shorter path to this node
        if current_distance > distances.get(current_node, math.inf):
            continue

        select(current_node)

        # Stop condition when we reach our target destination
        if current_node == target_node:
            break

        for neighbor in neighbors(current_node):
            edge_weight = weight(current_node, neighbor)
            distance = current_distance + edge_weight

            # Relaxation step: update if a shorter path is found
            if distance < distances.get(neighbor, math.inf):
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_node
                pq.append((distance, neighbor))

    # Reconstruct the shortest path
    path = []
    curr = target_node
    while curr in previous_nodes:
        path.insert(0, curr)
        curr = previous_nodes[curr]

    if path or start_node == target_node:
        path.insert(0, start_node)
        path_str = " -> ".join(path)
        visit(
            target_node,
            f"Shortest path found: {path_str} (Cost: {distances.get(target_node, 'N/A')})",
        )
    else:
        visit(start_node, f"No path found between {start_node} and {target_node}")


# Search path from node '1' to node '2'
dijkstra_shortest_path("1", "2")

Complexity

Dijkstra's efficiency depends heavily on the data structure used for the priority queue. Using a standard Min-Heap yields excellent performance.