Costs, Walks, and Distances
In an unweighted graph, the length of a path counts its edges. In a weighted digraph, each directed arc has a numerical cost, so two routes with the same number of arcs can have different total costs. A negative arc cost is allowed: it may make a route cheaper, but it does not by itself prevent a shortest route from existing. The key issue is whether a negative-cost cycle can be reached and then followed on the way to the destination.
Throughout, let \(G=(V,E)\) be a finite directed graph with a real cost \(w(u,v)\) assigned to each arc \((u,v)\). A directed walk is a sequence \(v_0,v_1,\ldots,v_k\) such that each \((v_{i-1},v_i)\) is an arc; vertices and arcs may repeat. Its cost is the sum of the costs of its arcs. A directed path is a directed walk with no repeated vertices. A directed cycle is a closed directed walk of positive length whose vertices are distinct apart from the repeated start and end. A vertex \(v\) is reachable from \(s\) if some directed walk from \(s\) to \(v\) exists, regardless of its cost.
The zero-length walk from a vertex to itself has cost \(0\), so \(d(s,s)\leq 0\) whenever a shortest-walk distance exists. If a negative-cost cycle can be reached from \(s\) and can then lead to \(s\), repeated trips around it make \(d(s,s)=-\infty\). Thus even the distance from a vertex to itself need not be zero when negative cycles are present.
What a Distance Label Says
A distance label is a value currently recorded for a vertex while a shortest-path problem is being worked on. A finite label is meaningful as a candidate cost when it is the cost of a particular known walk from the source. Such a label need not equal the true shortest-walk distance: another walk may have lower cost. A label of \(+\infty\) can mean that no candidate walk has yet been recorded; by itself, it does not prove that the vertex is unreachable. Only a fully determined distance of \(+\infty\) means that no walk exists.
When a shortest-walk distance is finite, the cost of every known walk from \(s\) to \(v\) is at least \(d(s,v)\). In particular, a valid finite candidate label cannot be smaller than the true distance. If the distance is \(-\infty\), however, no finite candidate can equal it: the label records one walk, while cheaper walks can be made by repeating a suitable negative cycle.
Worked Example: Candidate Labels Need Not Be Exact
Let the vertices be \(V=\{s,a,b,t\}\), with arcs and costs \(s\to a:4\), \(s\to b:2\), \(b\to a:1\), \(a\to t:3\), and \(b\to t:8\). Consider the candidate labels \(\ell(s)=0\), \(\ell(a)=4\), \(\ell(b)=2\), and \(\ell(t)=10\).
The labels come from these walks: the zero-length walk at \(s\) costs \(0\); \(s\to a\) costs \(4\); \(s\to b\) costs \(2\); and \(s\to b\to t\) costs \(2+8=10\). Each finite label is therefore the cost of a known walk.
To find the actual distances, compare the routes available. To \(a\), the direct walk costs \(4\), while \(s\to b\to a\) costs \(2+1=3\), so \(d(s,a)=3\). The only route to \(b\) costs \(2\), so \(d(s,b)=2\). The three \(s\)-to-\(t\) paths have costs \(s\to a\to t: 4+3=7\), \(s\to b\to t: 2+8=10\), and \(s\to b\to a\to t: 2+1+3=6\). Thus \(d(s,t)=6\).
Check: the graph has no directed cycle, so no walk can repeat a vertex; the listed routes include every possible \(s\)-to-\(t\) path. The labels \(4\) for \(a\) and \(10\) for \(t\) are valid candidate costs, but they exceed the distances \(3\) and \(6\).
Unreachable Vertices and Negative Edges
Reachability is determined by the directions of arcs, not by whether the costs are positive or negative. A vertex with a negative-cost outgoing arc may still be unreachable from the source. Conversely, a route containing a negative arc may be the cheapest route even when no negative cycle exists. In a graph with no negative-cost cycles on relevant routes, repeated portions of a walk can be removed without increasing its cost, so a minimum can be found among paths.
Worked Example: A Negative Arc and an Unreachable Vertex
Let \(V=\{s,a,b,c,z\}\), with arcs and costs \(s\to a:3\), \(a\to b:-1\), \(b\to c:4\), \(s\to c:10\), and \(z\to b:-7\). Starting from \(s\), determine the distances.
There is a walk \(s\to a\) of cost \(3\), so \(d(s,a)=3\). The route \(s\to a\to b\) costs \(3+(-1)=2\), so \(d(s,b)=2\). To reach \(c\), the route through \(a,b\) costs \(3+(-1)+4=6\), while the direct arc costs \(10\); hence \(d(s,c)=6\). No arc enters \(z\), so there is no walk from \(s\) to \(z\), and \(d(s,z)=+\infty\). The zero-length walk gives \(d(s,s)=0\).
Check: the graph has no directed cycle, so no repeated-vertex walk can produce an additional route. In particular, \(z\to b\) cannot be used from \(s\): the direction of that arc leads out of \(z\), and does not make \(z\) reachable.
When a Negative Cycle Destroys a Finite Distance
A cycle matters to a particular destination only if it can be reached from the source and the destination can be reached from the cycle. A negative cycle elsewhere in the graph does not affect every distance. The following result gives the exact distinction between a finite shortest-walk distance and an unbounded one.
Proof. If no \(s\)-to-\(v\) walk exists, the definition assigns \(+\infty\). Now suppose there is a negative cycle \(C\), a walk from \(s\) to a vertex of \(C\), and a walk from \(C\) to \(v\). Join these walks using \(C\), and traverse \(C\) an additional \(k\) times before continuing to \(v\). The resulting \(s\)-to-\(v\) walk has cost \(A+k\,w(C)+B\), where \(A\) and \(B\) are the fixed costs before and after the repetitions and \(w(C)<0\). As \(k\) grows, these costs tend to \(-\infty\), so no minimum exists.
It remains to suppose that an \(s\)-to-\(v\) walk exists but no negative cycle is both reachable from \(s\) and able to reach \(v\). A closed directed walk can be split into directed cycles: if it is not already a cycle, a repeated vertex divides it into shorter closed walks, and repeating this split terminates. The costs of the resulting cycles sum to the cost of the original closed walk. In any \(s\)-to-\(v\) walk, every repeated-vertex segment is a closed walk whose vertices are reachable from \(s\) and can reach \(v\). None of the cycles in its decomposition can have negative cost, by the supposition. Therefore the repeated-vertex segment has nonnegative cost. Deleting it leaves an \(s\)-to-\(v\) walk of no greater cost. Repeating deletions produces a path of no greater cost. There are only finitely many paths in a finite graph, so the least cost among the \(s\)-to-\(v\) paths exists. Since every walk can be reduced to a path of no greater cost, this least path cost is also a minimum over all walks. \(\square\)
Worked Example: A Negative Cycle Affects Only Some Destinations
Let \(V=\{s,a,b,c,t,q\}\), with arcs and costs \(s\to a:2\), \(a\to b:1\), \(b\to c:-4\), \(c\to a:1\), \(c\to t:5\), and \(s\to q:4\). The cycle \(a\to b\to c\to a\) has cost \(1+(-4)+1=-2\).
The cycle is reachable from \(s\) by \(s\to a\), and it can lead to \(t\) using \(c\to t\). A walk that traverses the cycle \(k\) times, then exits to \(t\), has cost \(2+k(-2)+1+(-4)+5=4-2k\). For \(k=0\) the cost is \(4\); for \(k=1\) it is \(2\); for \(k=2\) it is \(0\). Since \(4-2k\) decreases without bound as \(k\) increases, \(d(s,t)=-\infty\).
The same cycle can be reached and used to reach \(a,b,\) or \(c\), so their distances from \(s\) are also \(-\infty\). But \(q\) has no incoming arc, apart from the arc from \(s\), so the only \(s\)-to-\(q\) walk is \(s\to q\), of cost \(4\). Thus \(d(s,q)=4\). No arc returns to \(s\), so \(d(s,s)=0\).
Check: the cycle cost is \(1-4+1=-2\), and each extra traversal changes the displayed \(s\)-to-\(t\) walk cost by exactly \(-2\). The negative cycle cannot be used to reach \(q\), which is why its distance remains finite.
Common Pitfall: Restricting Attention to Paths
A path cannot repeat vertices, but a walk can. With nonnegative cycle costs, removing repeated portions is harmless when searching for a minimum. With a negative cycle, removing repetitions can discard exactly the cost reduction that makes walks arbitrarily cheap. In the last example, the simple \(s\)-to-\(t\) path \(s\to a\to b\to c\to t\) costs \(2+1-4+5=4\). It would be wrong to conclude that \(4\) is the shortest-walk distance: repeating the cycle gives costs \(2\), \(0\), and then still smaller values, with no minimum.
Another common mistake is to interpret every \(+\infty\) label as proof of unreachability. A label can be infinite simply because no candidate walk has yet been recorded. To conclude that a vertex is truly unreachable, one must know that no directed walk from the source exists. By contrast, a finite label tied to a known walk is evidence of reachability, but not proof that the label is optimal.
Check Your Understanding
Use directed walks and their costs in your answers. When considering a cycle, state whether it is reachable from the source and whether it can lead to the destination.
- A known walk to \(v\) has cost \(12\), while the current label is \(12\). What does this establish, and what does it not establish about \(d(s,v)\)?
- Can a vertex with a negative-cost outgoing arc still have distance \(+\infty\) from \(s\)? Give a reason based on arc directions.
- In the second example, compute the cost of \(s\to a\to b\to c\) and compare it with the direct route to \(c\).
- Suppose a negative cycle is reachable from \(s\) but there is no walk from that cycle to \(v\). Does that cycle alone force \(d(s,v)=-\infty\)? Explain.
- Why does the existence of a minimum-cost path not by itself establish a minimum over all walks when negative cycles are allowed?