Complexity

Choosing between shortest-path and MST algorithms is mostly a question of graph size, density and edge weights. This chapter derives the running times and compares the options.

Dijkstra

With a binary heap, every edge can cause at most one push, so the heap holds at most E + 1 entries. Each push and pop costs O(log E), and since E is at most V^2, log E is at most 2 log V. The total is O((V + E) log V) time and O(V + E) memory. Best, average and worst case have the same bound; an early exit for a single target only helps in practice.

For a dense graph (E close to V^2) the heap is not worth it. Scanning an array for the closest unfinished vertex costs O(V) per step and O(V^2) overall, which beats O(V^2 log V).

from math import inf

def dijkstra_dense(w, source):
    """w[u][v] is the edge weight, or inf if there is no edge."""
    n = len(w)
    dist = [inf] * n
    done = [False] * n
    dist[source] = 0
    for _ in range(n):
        u = min((i for i in range(n) if not done[i]), key=dist.__getitem__)
        if dist[u] == inf:
            break                      # the rest is unreachable
        done[u] = True
        for v in range(n):
            if dist[u] + w[u][v] < dist[v]:
                dist[v] = dist[u] + w[u][v]
    return dist

W = [[0, 4, 1], [inf, 0, inf], [inf, 2, 0]]
print(dijkstra_dense(W, 0))  # [0, 3, 1]

A Fibonacci heap lowers the bound to O(E + V log V), but its constant factors are large and it is rarely used outside theory.

Bellman-Ford, Floyd-Warshall and 0-1 BFS

• Bellman-Ford runs V - 1 rounds over all E edges: O(V E) time and O(V) memory. The early exit makes the best case O(E), when the first round already finds every distance.
• Floyd-Warshall always does V^3 iterations and stores a V × V matrix: O(V^3) time, O(V^2) memory. It is simple and fast for a few hundred vertices, but at V = 10^4 the matrix alone has 10^8 cells.
• 0-1 BFS processes each edge a constant number of times: O(V + E).

Directed acyclic graphs

If the graph has no cycles you do not need a heap at all, and negative weights are fine. Relax the edges in topological order; each edge is relaxed exactly once, for O(V + E) total. Python's standard library has a topological sorter.

from graphlib import TopologicalSorter
from math import inf

def dag_shortest(n, edges, source):
    adj = [[] for _ in range(n)]
    preds = {v: set() for v in range(n)}
    for u, v, w in edges:
        adj[u].append((v, w))
        preds[v].add(u)
    dist = [inf] * n
    dist[source] = 0
    for u in TopologicalSorter(preds).static_order():
        if dist[u] != inf:
            for v, w in adj[u]:
                dist[v] = min(dist[v], dist[u] + w)
    return dist

print(dag_shortest(4, [(0, 1, 5), (0, 2, 3), (2, 1, -4), (1, 3, 1)], 0))  # [0, -1, 3, 0]