Four Algorithms, Different Tasks
Shortest-path algorithms are not interchangeable: each makes different assumptions about edge weights or graph structure, and their outputs answer different questions. Dijkstra’s algorithm is suited to a single source when all edge weights are nonnegative. Bellman–Ford handles negative weights and can detect a negative cycle reachable from the source. Topological-order relaxation uses the stronger structural condition that the directed graph is acyclic. Floyd–Warshall computes distances between every pair of vertices, using a table of quadratic size.
Throughout, a weighted directed graph is a finite directed graph \(G=(V,E)\) together with a real weight \(w(e)\) for each edge. A directed walk is a sequence of edges in which each edge starts where the previous one ends; vertices may repeat. Its weight is the sum of its edge weights. A directed path is a walk with no repeated vertex. The distance from \(u\) to \(v\) is the infimum of the weights of walks from \(u\) to \(v\). It is a minimum when some walk attains it, and a shortest path is such a walk with no repeated vertex. If there is no walk from \(u\) to \(v\), we write the distance as \(\infty\). A negative cycle is a directed cycle whose total weight is negative. If a negative cycle is reachable from the source, then every vertex reachable from that cycle has distance \(-\infty\): a walk can go around the cycle repeatedly to make its weight arbitrarily small, so no minimum exists.
For a single-source algorithm, the source \(s\) is assumed to be a vertex of \(G\). If \(V\) is empty, there is no source to specify; an all-pairs algorithm instead returns an empty distance table. The complexity comparisons below use adjacency lists for the graph, an indexed binary heap for Dijkstra’s algorithm, and count memory for the graph representation and algorithm data together. Asymptotic bounds describe the general case; a one-vertex graph takes constant time.
What Each Algorithm Requires and Returns
| Algorithm | Input condition | Output | Time and memory |
|---|---|---|---|
| Dijkstra | One source; every edge weight is nonnegative. | Distances and, with predecessor pointers, paths from the source. | \(O((n+m)\log n)\) time; \(O(n+m)\) memory. |
| Bellman–Ford | One source; edge weights may be negative. | Distances and paths if no negative cycle is reachable from the source; otherwise it reports such a cycle. | \(O(nm+n+m)\) worst-case time; \(O(n+m)\) memory. |
| Topological-order relaxation | One source in a directed acyclic graph (DAG); weights may be negative. | Distances and paths from the source. | \(O(n+m)\) time; \(O(n+m)\) memory. |
| Floyd–Warshall | All pairs; negative edge weights are allowed. For finite shortest-path distances between all reachable pairs, assume there is no negative cycle. | An \(n\)-by-\(n\) table of all-pairs distances; a next-vertex or predecessor table can also reconstruct paths. | \(O(n^3)\) time; \(O(n^2)\) memory. |
Here \(n=|V|\) and \(m=|E|\). “Memory” includes storing the input graph. For Dijkstra, using an adjacency matrix instead of adjacency lists gives a simple \(O(n^2)\)-time implementation, but the matrix itself uses \(O(n^2)\) memory. The bounds for the other single-source methods can also include a predecessor array using \(O(n)\) additional space. Floyd–Warshall’s distance table is already quadratic in size because it records one value for each ordered pair.
For a disconnected graph, a single-source method assigns \(\infty\) to vertices that cannot be reached from its source; it does not automatically find distances from other sources. In a DAG, topological ordering processes every vertex once in an order in which each edge goes from an earlier vertex to a later one. Relaxing an edge \(u v\) means testing whether the current estimate at \(v\) can be reduced to \(d(u)+w(uv)\), when \(d(u)\) is finite.
Why the Time and Memory Bounds Differ
Dijkstra’s algorithm scans each outgoing edge when its tail is settled. With adjacency lists, these scans account for \(O(m)\) edge examinations. An indexed binary heap supports extracting a minimum label and updating a label in \(O(\log n)\) time; there are at most \(n\) extractions and at most \(m\) successful edge-based updates. This gives \(O((n+m)\log n)\) time. The graph, distance and predecessor arrays, and heap use \(O(n+m)\) memory. The nonnegative-weight condition is essential to the settled-vertex guarantee: a later route cannot improve a vertex once it has been settled.
Bellman–Ford makes at most \(n-1\) full passes over the edges, then can make one more pass to test for a reachable negative cycle. Its main work is therefore \(O(nm)\), together with initialization and graph storage, giving \(O(nm+n+m)\) in a bound that also covers sparse or edgeless inputs. It stores a distance and often a predecessor for each vertex, so its memory remains \(O(n+m)\). The reason \(n-1\) passes suffice when no reachable negative cycle exists is that a shortest route can be chosen without repeated vertices, hence uses at most \(n-1\) edges.
Topological-order relaxation initializes the labels, scans each vertex in topological order, and examines each outgoing edge once. Finding a topological order and performing these scans take \(O(n+m)\) time; the graph and arrays take \(O(n+m)\) memory. Negative weights cause no difficulty because the DAG order ensures that all possible predecessors of a vertex are processed before that vertex.
Floyd–Warshall considers each vertex as a possible intermediate vertex for every ordered pair. There are \(n\) rounds, and each round examines \(n^2\) pairs, giving \(O(n^3)\) time. It stores the current distance table in \(O(n^2)\) space. A separate next-vertex table for reconstructing paths adds another \(O(n^2)\) entries, without changing the asymptotic bound.
Proof. For Dijkstra, scanning adjacency lists examines \(m\) edges, and the indexed binary heap performs at most \(n\) minimum extractions and \(m\) successful updates, each costing \(O(\log n)\). The heap and vertex arrays use \(O(n)\) space, in addition to the \(O(n+m)\)-space graph. Bellman–Ford performs at most \(n\) passes when the negative-cycle test is included, with \(m\) edge examinations per pass, plus initialization and storage; this is \(O(nm+n+m)\) time and \(O(n+m)\) memory. A topological-order computation and the subsequent relaxation each scan vertices and edges a constant number of times, giving \(O(n+m)\) time and memory. Floyd–Warshall performs \(n\) rounds of \(n^2\) pair updates and stores an \(n\)-by-\(n\) table, giving \(O(n^3)\) time and \(O(n^2)\) memory. \(\square\)
Worked Traces
Worked Example: Dijkstra from One Source
Let \(V=\{s,a,b,t\}\) and \(E=\{sa,sb,ba,at,bt\}\), with directed edge weights \(w(sa)=4\), \(w(sb)=1\), \(w(ba)=2\), \(w(at)=1\), and \(w(bt)=5\). All weights are nonnegative, so Dijkstra’s algorithm applies. Start with \(d(s)=0\) and \(d(a)=d(b)=d(t)=\infty\).
| Step | Vertex settled | Relaxations and labels after the step |
|---|---|---|
| 1 | \(s\), label \(0\) | \(d(a)=\min(\infty,0+4)=4\); \(d(b)=\min(\infty,0+1)=1\); \(d(t)=\infty\). |
| 2 | \(b\), label \(1\) | \(d(a)=\min(4,1+2)=3\); \(d(t)=\min(\infty,1+5)=6\). |
| 3 | \(a\), label \(3\) | \(d(t)=\min(6,3+1)=4\). |
| 4 | \(t\), label \(4\) | No outgoing edges; all vertices are settled. |
The resulting distances are \(d(s)=0\), \(d(b)=1\), \(d(a)=3\), and \(d(t)=4\). The predecessor pointers give paths \(s\), \(s b\), \(s b a\), and \(s b a t\), respectively. Check: the path weights are \(0\), \(1\), \(1+2=3\), and \(1+2+1=4\). The other route to \(t\) through \(b\) has weight \(1+5=6\), and the route \(s a t\) has weight \(4+1=5\), both larger than \(4\).
Worked Example: Negative Edges in a DAG
Let \(V=\{s,a,b,c\}\) and \(E=\{sa,sb,ab,ac,bc\}\), with weights \(w(sa)=4\), \(w(sb)=5\), \(w(ab)=-2\), \(w(ac)=4\), and \(w(bc)=3\). This is a DAG: \(s,a,b,c\) is a topological order. The negative edge means Dijkstra’s nonnegative-weight condition is not met. Both Bellman–Ford and topological-order relaxation apply.
For topological-order relaxation, initialize \(d(s)=0\) and the other labels to \(\infty\). Processing \(s\) gives \(d(a)=4\) and \(d(b)=5\). Processing \(a\) gives \(d(b)=\min(5,4-2)=2\) and \(d(c)=\min(\infty,4+4)=8\). Processing \(b\) gives \(d(c)=\min(8,2+3)=5\). Processing \(c\) makes no change. Thus the output labels are \(0,4,2,5\) for \(s,a,b,c\).
For Bellman–Ford, order the edge scans as \(sa,sb,ab,ac,bc\). In pass 1, the successive finite updates are \(d(a)=4\), \(d(b)=5\), \(d(b)=2\), \(d(c)=8\), and \(d(c)=5\). Pass 2 makes no change: the candidates are \(d(a)=4\), \(d(b)=5\), \(d(b)=2\), \(d(c)=8\), \(d(c)=5\), and each is at least the current label at its destination. Pass 3 also makes no change, since it repeats the same candidates. The algorithm may stop after pass 2 if it uses early termination.
Check: the paths \(s\), \(sa\), \(sab\), and \(sabc\) have weights \(0\), \(4\), \(4-2=2\), and \(4-2+3=5\). The other path to \(c\), \(sac\), has weight \(4+4=8\), and \(sbc\) has weight \(5+3=8\). These agree with the computed labels. Bellman–Ford makes up to \(n-1=3\) relaxation passes because \(n=4\); topological relaxation obtains the same answers in one ordered scan.
Worked Example: Floyd–Warshall for All Pairs
Let \(V=\{1,2,3\}\) and \(E=\{12,13,23,31\}\), with weights \(w(12)=4\), \(w(13)=10\), \(w(23)=-2\), and \(w(31)=3\). There is a negative edge, but the directed cycle \(1\to2\to3\to1\) has weight \(4-2+3=5\), so it is not negative. The other simple directed cycle is \(1\to3\to1\), of weight \(10+3=13\). Neither cycle is negative, so there is no negative cycle.
In the matrices below, rows are starting vertices and columns are destinations. Initially, diagonal entries are \(0\), direct-edge entries are their weights, and absent-edge entries are \(\infty\). \(D^{(k)}[i,j]\) denotes the table value after considering the first \(k\) vertices in the order \(1,2,3\) as allowable intermediate vertices.
Using vertex \(1\), the update \(D^{(1)}[i,j]=\min(D^{(0)}[i,j],D^{(0)}[i,1]+D^{(0)}[1,j])\), when both terms in the sum are finite, changes \(3\to2\) to \(3+4=7\), and \(3\to3\) to the candidate \(3+10=13\), which is larger than \(0\). The other finite candidates do not improve their entries. Thus
Using vertex \(2\), the route \(1\to2\to3\) changes the entry \(1\to3\) from \(10\) to \(4+(-2)=2\). The route \(3\to2\) cannot be improved through \(2\), since \(D^{(1)}[3,2]+D^{(1)}[2,2]=7+0=7\). Therefore
Using vertex \(3\), the route \(2\to3\to1\) changes \(2\to1\) from \(\infty\) to \(-2+3=1\). The candidate for \(1\to1\) is \(2+3=5\), which does not improve \(0\); the candidate for \(3\to2\) is \(0+7=7\), which leaves \(7\) unchanged. The final table is
Check: the entries \(1\to3\), \(2\to1\), and \(3\to2\) are realized by paths of weights \(4-2=2\), \(-2+3=1\), and \(3+4=7\), respectively. The direct path \(1\to3\) of weight \(10\) is longer than \(1\to2\to3\), as the table records. Floyd–Warshall returns all nine ordered-pair distances in one table, rather than running a single-source method separately from each vertex.
What Floyd–Warshall Means When There Is a Negative Cycle
The intermediate-vertex recurrence has a shortest-path interpretation when there is no negative cycle. In that case, if a path repeats a vertex, the segment between two visits is a cycle of nonnegative weight; removing that segment does not increase the path’s weight. A minimum can therefore be attained by a path with no repeated vertices. Splitting such a path according to whether it uses the newly allowed intermediate vertex proves the recurrence: it either avoids that vertex, or splits into a route to it and a route from it. This is the standard correctness argument for the Floyd–Warshall recurrence under the no-negative-cycle condition.
Proof. Assume the graph has no negative cycle and that the first \(k-1\) vertices in the fixed order have already been allowed as intermediates. Consider a shortest path from \(i\) to \(j\) whose internal vertices are among the first \(k\). A shortest path may be chosen without repeated vertices: if a vertex repeats, the intervening closed portion is a sum of cycles, each of nonnegative weight, and deleting it does not increase the weight. If the chosen path avoids vertex \(k\), its best possible weight is \(D^{(k-1)}[i,j]\). If it uses \(k\), it uses it at most once, and splits into an \(i\)-to-\(k\) portion and a \(k\)-to-\(j\) portion whose internal vertices are among the first \(k-1\). The best weight of this kind is \(D^{(k-1)}[i,k]+D^{(k-1)}[k,j]\), when both parts are reachable. Taking the smaller of the available cases gives the recurrence. If no route exists, the value is \(\infty\). \(\square\)
With a negative cycle, the table can still be computed and used to detect negative cycles: a negative diagonal entry indicates that a vertex can return to itself with negative total weight. But the table entries must not then be described as minimum path weights. The repeated-cycle example below shows why.
Worked Example: A Negative Cycle Changes the Interpretation
Let \(V=\{x,y\}\), with directed edges \(xy\) of weight \(-2\) and \(yx\) of weight \(1\), in the order \(x,y\). The cycle \(x\to y\to x\) has weight \(-2+1=-1\). Initially,
After allowing \(x\), the table update gives \(D^{(1)}[y,y]=\min(0,1+(-2))=-1\). After allowing \(y\), it gives \(D^{(2)}[x,y]=\min(-2,(-2)+(-1))=-3\). The value \(-3\) is a table value, not a minimum weight for an \(x\)-to-\(y\) walk: taking the cycle first and then going from \(x\) to \(y\) gives weight \(-1-2=-3\), and repeating the negative cycle more times gives still smaller weights. There is no finite minimum. The negative diagonal value \(-1\) records the negative cycle.
Common Pitfall and Practical Comparison
Do not use Dijkstra’s settled labels when weights can be negative. For a concrete failure, let \(V=\{s,a,b\}\), with directed edges \(sa\) of weight \(2\), \(sb\) of weight \(5\), and \(ba\) of weight \(-10\). Dijkstra first settles \(s\), assigning \(d(a)=2\) and \(d(b)=5\), then settles \(a\) at \(2\). When it later settles \(b\), relaxing \(ba\) proposes \(5-10=-5\) for \(a\), but \(a\) has already been settled. The true shortest route to \(a\) is \(s\to b\to a\), of weight \(5-10=-5\), not \(2\). The correction is to use Bellman–Ford for general edge weights, or topological-order relaxation if the graph is a DAG.
Choose based on the task as well as the weights. For one source with nonnegative weights, Dijkstra is generally efficient. For one source with negative weights, Bellman–Ford is the general option and can report a reachable negative cycle. If the graph is acyclic, topological relaxation is linear-time even when some weights are negative. For distances among all pairs, Floyd–Warshall is direct and has quadratic memory use; its distance interpretation requires the absence of negative cycles. In particular, a computed table alone does not turn an undefined shortest-path minimum into a finite distance.
Check Your Understanding
For each question, state any input condition needed before giving the answer.
- Which algorithm would you use to find distances from one source in a graph with nonnegative weights, and what is its standard adjacency-list running time with an indexed binary heap?
- Why can Bellman–Ford handle negative edge weights, and what does it report if a negative cycle is reachable from the source?
- Explain why topological-order relaxation applies to a DAG with negative edges and give its running-time bound.
- What are the time and memory bounds for Floyd–Warshall, and what does a negative diagonal entry indicate?
- In a graph with a negative cycle, why should Floyd–Warshall table entries not be called minimum path weights?