Dijkstra's Algorithm

Goal

Find the shortest path from a source node to all other nodes in a graph with non-negative edge weights.

Setup

Graph can be directed or undirected. Edge weights must be nonnegative. Let: $G=(V,E)$, where $w(u,v)\ge 0$ and $s\in V$ (s is the starting node) We use two key data structures:

1. dist[] is a distance array where dist[v] = shortest distance from source to v. We initialize this to infinity for all nodes except dist[s] = 0
2. Priority Queue / Min Heap: always pick the unvisited node with the smallest tentative distance

Algorithm

1. Initialize dist[v] = infinity for all nodes $v\in V$; set dist[s]=0
2. Insert all nodes into a min-priority queue with their distances
3. while the queue is not empty:
4. Extract the node $u$ with minimum dist[u]
5. For each neighbor $v$ of $u$:
   1. If going through $u$ improves the distance to $v$: $\text{ if }dist[u]+w(u,v)<dist[v]\text{ then }dist[v]=dist[u]+w(u,v)$
   2. Update the priority queue with new dist[v] 4. dist[] now contains the shortest distances from s to every other node.

import heapq
from collections import defaultdict
 
def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
 
    # Min-heap: (distance, node)
    pq = [(0, start)]
 
    while pq:
        current_dist, u = heapq.heappop(pq)
 
        # Skip if we found a better path already
        if current_dist > dist[u]:
            continue
 
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))
 
    return dist