Shortest paths (Dijkstra)

Always take the shortest known path, expanding outward until the destination is reached.

The idea

In a weighted graph, BFS doesn't work because a path with 5 edges might be "shorter" (cheaper) than a path with 1 edge. Dijkstra's Algorithm fixes this by using a Priority Queue.

We keep track of the shortest known distance to every node (initially infinity). We pop the closest known node from the Priority Queue, and from there, we check all its neighbors. If we find a strictly shorter path to a neighbor, we update its distance and push it into the Priority Queue.

Note: Dijkstra fails if there are negative edge weights. For that, you need Bellman-Ford.

Priority Queue: [(dist=0, A)]

Dijkstra initialized. Start node A has distance 0.

How it works (Dijkstra)

import heapq

def dijkstra(graph, start):
    distances = {n: float('inf') for n in graph}
    distances[start] = 0
    pq = [(0, start)] # (distance, node)
    
    while pq:
        curr_dist, curr_node = heapq.heappop(pq)
        
        # If we pulled a stale entry from PQ, ignore it
        if curr_dist > distances[curr_node]:
            continue
            
        for neighbor, weight in graph[curr_node]:
            dist = curr_dist + weight
            if dist < distances[neighbor]:
                distances[neighbor] = dist
                heapq.heappush(pq, (dist, neighbor))
                
    return distances