Choosing And Applying A Shortest-Path Algorithm

Choosing an Algorithm from the Problem

A shortest-path problem is specified not just by a graph, but also by what is being asked: one source to all reachable vertices, one source to a particular target, or distances between every pair. The edge weights and the graph’s structure matter too. Dijkstra’s algorithm applies when all edge weights are nonnegative; topological-order relaxation applies to directed acyclic graphs, even if some weights are negative; Bellman–Ford handles negative weights and detects reachable negative cycles; and Floyd–Warshall computes all-pairs distances.

All graphs below are finite weighted directed graphs. A directed walk from \(s\) to \(v\) is a sequence of vertices joined by directed edges from each vertex to the next; its weight is the sum of those edge weights. A directed path is a directed walk with no repeated vertices. A directed cycle is a positive-length closed directed walk with no repeated vertices except its first and last. A cycle is negative if the sum of its edge weights is less than zero.

A negative cycle is relevant to the pair \((s,v)\) if it can be reached from \(s\) and \(v\) can be reached from that cycle. Repeating such a cycle makes the weight of an \(s\)-to-\(v\) walk arbitrarily small. This is why distances must be defined using walks, not just paths.

Why the Main Choices Work

Proof. Maintain tentative labels, initially \(0\) at \(s\) and \(\infty\) elsewhere. When a vertex \(u\) is settled, relax each outgoing edge \(uw\) by replacing the label of \(w\) by the smaller of its current label and the label of \(u\) plus the weight of \(uw\). Every finite tentative label is the weight of an actual walk from \(s\), so it is at least \(d(s,w)\). We prove by induction on the settling order that each settled label is its true distance. This holds for \(s\), since all edge weights are nonnegative and no walk from \(s\) back to \(s\) has negative weight. Now let \(u\) be the next unsettled vertex with least finite label. Take a shortest path from \(s\) to \(u\), which exists because nonnegative cycles can be removed without increasing a walk’s weight. Let \(x\) be the first unsettled vertex on this path and \(y\) its predecessor. The predecessor \(y\) is settled, so by induction its label is \(d(s,y)\). When \(y\) was settled, relaxing \(yx\) gave \(x\) a label at most the weight of the path prefix from \(s\) to \(x\). That prefix has weight at most \(d(s,u)\), because the remaining path edges have nonnegative weights. Thus \(u\)’s label, being no greater than \(x\)’s label, is at most \(d(s,u)\). It is also at least \(d(s,u)\), since it is the weight of a walk. Equality follows. If no finite unsettled label remains, no unsettled vertex is reachable: any path to one would have a first unsettled vertex reached by an edge from a settled vertex, which would have received a finite label. \(\square\)

Proof. A topological order lists the vertices so that every directed edge goes from an earlier vertex to a later one. For each vertex \(v\), every path from \(s\) to \(v\) ends with an edge \(uv\) whose tail \(u\) occurs earlier. When \(u\) is processed, its distance has already been computed, so relaxing \(uv\) considers the weight of every such path. Taking the minimum over incoming edges therefore gives the minimum path weight to \(v\). If \(v=s\), the empty walk has weight \(0\), which is included as a candidate; if no path reaches \(v\), its label stays \(\infty\). A directed acyclic graph has no directed cycles, so no walk can revisit a vertex; the minimum over walks is thus obtained among paths. The argument uses the order of edges, not the signs of their weights. \(\square\)

Worked Examples

All-Pairs Queries and Floyd–Warshall

When the question asks for distances between every ordered pair, Floyd–Warshall systematically allows more vertices as intermediate points. Number the vertices \(v_1,\ldots,v_n\). Let \(D^{(k)}[i,j]\) be the minimum weight of a \(v_i\)-to-\(v_j\) path whose internal vertices are among \(v_1,\ldots,v_k\). With no allowed intermediate vertices, the entries are \(0\) on the diagonal, the edge weight for a direct edge, and \(\infty\) when there is no direct edge. The update is

This recurrence compares paths that do not use \(v_k\) internally with paths that do. When there is no negative cycle, a shortest walk can be chosen as a path, so it uses \(v_k\) at most once internally; splitting there gives the second candidate. A negative cycle means some all-pairs distances may be \(-\infty\), so ordinary finite-distance output must be interpreted with that condition in mind.

Common Pitfall: Applying Dijkstra with a Negative Edge

Dijkstra’s method is not justified merely because the graph is directed or because most weights are positive. For a concrete failure, take \(V=\{s,a,b,t\}\) with edges \(s\to a\) of weight \(2\), \(s\to b\) of weight \(5\), \(b\to a\) of weight \(-6\), \(a\to t\) of weight \(2\), and \(b\to t\) of weight \(1\). If Dijkstra settles \(a\) at label \(2\), it can give \(t\) label \(2+2=4\), then settle \(t\) before \(b\), whose label is \(5\). But the path \(s\to b\to a\to t\) has weight \(5-6+2=1\), so \(4\) is wrong. The correction is to check the weight condition before choosing the method: this graph has a negative edge, so use Bellman–Ford (or a specialized method if its structure permits one).

For a reliable choice, first determine whether the query is single-source or all-pairs. For a single source, check whether all weights are nonnegative; if so, Dijkstra applies. If negative weights occur, check whether the graph is acyclic; if it is, use topological-order relaxation. Otherwise use Bellman–Ford and interpret any detected negative cycle in relation to the target vertices. For all-pairs queries, use Floyd–Warshall and check whether negative cycles affect the pairs of interest. After computing, verify path weights from their edges and compare each label with the relevant incoming-edge candidates.