Shortest paths (Dijkstra)

In a weighted graph, the shortest path is the one with the smallest total weight, not the fewest edges. Dijkstra's algorithm solves the single-source version: given a start node, find the cheapest distance to every other node.

It keeps a tentative distance for every node (infinity at first, 0 for the source) and a min-heap of (distance, node). It repeatedly takes the node with the smallest tentative distance. Because all weights are non-negative, no later path can make that node cheaper, so its distance is final. It then relaxes the node's edges: if going through it makes a neighbour cheaper, update the neighbour and push it.

With a binary heap it runs in O((V + E) log V). It requires non-negative weights. With negative weights use Bellman-Ford, O(V x E); for all pairs on small graphs use Floyd-Warshall, O(V^3); for unweighted graphs plain BFS is enough.

1. 1Set dist[source] = 0 and every other distance to infinity. Push (0, source) onto a min-heap.
2. 2Pop the entry with the smallest distance d for node u. If d is larger than dist[u], it is stale (a cheaper path was already found): skip it.
3. 3Otherwise u is settled. For each edge u to v with weight w, compute d + w. If it is smaller than dist[v], set dist[v] = d + w, record u as v's parent, and push (d + w, v).
4. 4Repeat until the heap is empty, or stop early when the target is popped if you only need one destination.
5. 5Rebuild the path by following parent pointers back from the target.
6. 6The algorithm is correct because, with non-negative weights, the smallest tentative distance cannot be improved by going through any node that is farther away.

import heapq

def dijkstra(n, adj, src):
    # adj[u] = list of (v, weight), every weight >= 0
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                  # stale entry: u already settled cheaper
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:          # relax the edge
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist                       # inf means unreachable

Python's heapq has no decrease-key, so the code pushes a new entry on every improvement and skips stale ones when popped (lazy deletion). The heap holds at most O(E) entries, giving O((V + E) log V) time and O(V + E) space.

Cost: O((V + E) log V) with a binary heap and O(V + E) space. Bellman-Ford O(V x E). Floyd-Warshall O(V^3) time, O(V^2) space.