Shortest Paths: Dijkstra, Bellman-Ford, 0-1 BFS

Concept

Unweighted graph → plain BFS. Weights 0/1 → 0-1 BFS with a deque. Non-negative weights → Dijkstra with a min-heap. Negative weights → Bellman-Ford (also detects negative cycles).

Dijkstra repeatedly pops the closest unfinished node and relaxes its edges: if dist[u] + w < dist[v], update dist[v] and push it.

Bellman-Ford relaxes every edge V-1 times. If an edge can still be relaxed after that, a negative cycle exists. Floyd-Warshall gives all-pairs shortest paths in O(V³).

Complexity

Code (Python)

import heapq

def dijkstra(n, edges, src):
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                 # stale entry
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

def bellman_ford(n, edges, src):
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle")
    return dist

Remember

• Dijkstra fails with negative edges.
• Skip stale heap entries (d > dist[u]).
• 'At most K stops' → Bellman-Ford limited to K+1 rounds.