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]

Kruskal and Prim

• Kruskal sorts the edges in O(E log E); the union-find operations with path compression (or halving) and union by size cost O(E α(V)), where the inverse Ackermann function α is below 5 for any practical input. Sorting dominates, so the total is O(E log E), the same as O(E log V).
• Prim with a binary heap is O(E log V), like Dijkstra. With an adjacency matrix and an array instead of a heap it is O(V^2), the best choice for complete graphs such as "connect every pair of points".

Comparison table

For all-pairs on a sparse graph with non-negative weights, running Dijkstra from every vertex costs O(V (V + E) log V), which beats Floyd-Warshall when E is much smaller than V^2. Johnson's algorithm extends that idea to negative edges by reweighting with one Bellman-Ford pass.

A sense of scale

V = 10,000 vertices, E = 100,000 edges, log2 V is about 14

Dijkstra (binary heap)   (V + E) log V   about 1.5 million steps
Bellman-Ford             V × E           1,000,000,000 steps
Floyd-Warshall           V^3             1,000,000,000,000 steps
Kruskal                  E log E         about 1.7 million steps

Rough step counts are not seconds, but they show why the right choice matters by several orders of magnitude.

Summary

• Dijkstra: O((V + E) log V) with a heap, O(V^2) with an array for dense graphs.
• Bellman-Ford is O(V E) and the price of allowing negative edges; Floyd-Warshall is O(V^3) and only fits small graphs.
• DAGs and 0/1 weights admit linear-time algorithms.
• Kruskal is dominated by sorting; Prim mirrors Dijkstra's heap structure.