Weighted Directed Graphs
In an unweighted graph, a path’s length counts its edges. In a weighted digraph, each directed arc has a numerical weight, so routes are compared by their total costs instead. This distinction is useful whenever moving from one location to another has direction-dependent costs, such as travel times, prices, or gains and losses. A shortest-path problem asks for the least possible cost between specified vertices, but the answer depends on which vertices are allowed to be repeated and whether negative-cost cycles are present.
A directed walk from \(s\) to \(v\) is a sequence \(v_0,v_1,\ldots,v_k\) with \(v_0=s\), \(v_k=v\), and an arc \(v_{i-1}\to v_i\) for every \(1\le i\le k\). Vertices may repeat. A directed path is a directed walk with no repeated vertices. The empty walk at a vertex has length zero and cost zero; it is the path from that vertex to itself.
For vertices \(s,v\), the source-to-vertex shortest-path distance \(d_w(s,v)\) is the infimum of the costs of all directed walks from \(s\) to \(v\). If there is no such walk, define \(d_w(s,v)=+\infty\). If walk costs can be made arbitrarily negative, define \(d_w(s,v)=-\infty\). When \(d_w(s,v)\) is finite, a shortest path means a directed path with no repeated vertices whose cost equals \(d_w(s,v)\). The distinction matters: a walk with repeated vertices is not a path, even if it has minimum cost.
Finite Distances and Shortest Paths
Proof. Suppose a walk \(W\) from \(s\) to \(v\) contains a repeated vertex: its sequence has \(v_i=v_j\) for some \(i<j\). The portion from \(v_i\) to \(v_j\) is a closed segment. If that segment has cost \(c<0\), then we can follow the walk up to \(v_i\), traverse the closed segment any number \(q\) of additional times, and then follow the rest of \(W\). These are all walks from \(s\) to \(v\), and their costs are \(w(W)+qc\). Since \(c<0\), these costs have no lower bound as \(q\) increases. Thus \(d_w(s,v)=-\infty\).
Now suppose \(d_w(s,v)\) is finite. No walk from \(s\) to \(v\) can contain a negative closed segment, by the argument just given. In any such walk, every repeated-vertex segment therefore has cost at least zero. Deleting that segment leaves a walk with the same endpoints and cost no greater than before. Repeating this deletion reduces the walk to a directed path, because each deletion shortens the walk and the process ends when no vertex repeats. There are only finitely many directed paths in a finite graph: each uses distinct vertices, so its length is at most \(|V|-1\), and the graph has finitely many arcs. Since \(v\) is reachable, at least one such path exists. The finite set of path costs therefore has a minimum. Every walk can be reduced to a path of no greater cost, so this minimum is also the infimum over all walks. A path attaining \(d_w(s,v)\) exists. \(\square\)
This result explains why the word “path” in “shortest path” must be used precisely. A repeated-vertex walk might attain a finite distance—for example, if it includes a zero-cost cycle—but it is not itself a path. The theorem guarantees that when the distance is finite, some path without repeated vertices attains the same cost.
Single-Source and All-Pairs Questions
A single-source answer is one list of distances, one entry per destination, and may also record paths that attain finite entries. An all-pairs answer is a table with one row for each starting vertex and one column for each destination. Solving a single-source problem from each vertex would produce all rows, but the two problem statements ask for different amounts of output. In either setting, an unreachable destination has distance \(+\infty\); a destination whose walk costs are unbounded below has distance \(-\infty\).
Worked Example: Distances from One Source
Let \(G\) have vertex set \(V=\{s,a,b,t,u\}\) and arc set with weights \(s\to a:4,\ s\to b:2,\ b\to a:1,\ a\to t:3,\ b\to t:7\). There are no other arcs. Find the distances from \(s\).
Starting at \(s\), the empty path to \(s\) costs \(0\). The only path to \(b\) is \(s\to b\), of cost \(2\). The paths to \(a\) are \(s\to a\), of cost \(4\), and \(s\to b\to a\), of cost \(2+1=3\), so \(d_w(s,a)=3\).
The paths to \(t\) are \(s\to a\to t\), with cost \(4+3=7\); \(s\to b\to t\), with cost \(2+7=9\); and \(s\to b\to a\to t\), with cost \(2+1+3=6\). Thus \(d_w(s,t)=6\), attained by \(s\to b\to a\to t\). No arc enters or leaves \(u\), so there is no walk from \(s\) to \(u\), and \(d_w(s,u)=+\infty\).
Check: the single-source distance list, in the order \(s,a,b,t,u\), is \(0,3,2,6,+\infty\). Each finite entry is attained by the path \(s\), \(s\to b\to a\), \(s\to b\), or \(s\to b\to a\to t\), respectively. The listed paths use only arcs in the defined arc set, and the only candidate paths to \(a\) and \(t\) have been compared.
Negative Weights and Unbounded Costs
A negative arc does not, by itself, make a shortest-path distance unbounded below. For that to happen, a walk must be able to repeat a negative-cost closed segment while still reaching the destination. Conversely, a negative closed segment that lies on a route from \(s\) to \(v\) can be traversed repeatedly, lowering the cost without limit. The next example has a negative arc but no directed cycle, so every source-to-destination route is finite in number.
Worked Example: A Negative Arc Without a Negative Cycle
Let \(G\) have vertex set \(V=\{s,a,b,t\}\) and weighted arc set \(s\to a:4,\ s\to b:5,\ b\to a:-3,\ a\to t:2,\ b\to t:6\). There are no other arcs. Find the distances from \(s\).
The path to \(b\) is \(s\to b\), with cost \(5\). The two paths to \(a\) cost \(4\) along \(s\to a\), and \(5+(-3)=2\) along \(s\to b\to a\). Therefore \(d_w(s,a)=2\), attained by the second path.
The paths to \(t\) have costs \(4+2=6\) along \(s\to a\to t\), \(5+6=11\) along \(s\to b\to t\), and \(5+(-3)+2=4\) along \(s\to b\to a\to t\). Hence \(d_w(s,t)=4\). The graph has no directed cycle: every arc moves forward in the order \(s,b,a,t\), except that the direct arc \(s\to a\) also moves forward. Thus no closed segment can be repeated.
Check: the distance list in the order \(s,a,b,t\) is \(0,2,5,4\). The path costs just computed attain the three nonzero entries, and the direct path \(s\to a\) costs \(4\), which is greater than the alternative cost \(5+(-3)=2\). This confirms that the negative arc improves a route without making its cost unbounded.
For a finite distance, the distance is attained and can be represented by a shortest path, as proved above. If a negative closed segment occurs on an \(s\)-to-\(v\) walk, repeating it instead makes the distance \(-\infty\); in that case there is no minimum-cost walk or shortest path. These alternatives are different from \(+\infty\), which means that \(v\) cannot be reached from \(s\) at all.
Worked Example: A Reachable Negative Cycle
Let \(G\) have vertex set \(V=\{s,a,b,t\}\) and weighted arc set \(s\to a:2,\ a\to b:1,\ b\to a:-3,\ b\to t:4\). There are no other arcs. Determine \(d_w(s,t)\).
The closed walk \(a\to b\to a\) has cost \(1+(-3)=-2\). There is a route from \(s\) to this closed walk, namely \(s\to a\), and a route from it to \(t\), namely \(b\to t\). For each integer \(q\ge0\), take the walk that follows \(s\to a\), traverses \(a\to b\to a\) exactly \(q\) times, then takes \(a\to b\to t\). Its cost is \(2+q(-2)+1+4=7-2q\).
For example, \(q=0\) gives cost \(7\), \(q=1\) gives \(5\), and \(q=2\) gives \(3\). In general, for any real lower bound \(M\), choosing an integer \(q>(7-M)/2\) gives \(7-2q<M\). Therefore the costs are unbounded below, and \(d_w(s,t)=-\infty\). No path can be a shortest path for this pair: each path has no repeated vertices, while the walks above have costs decreasing without bound.
Check: each additional traversal contributes exactly \((-3)+1=-2\), so the cost changes from \(7\) to \(7-2q\) as stated. The cycle is reachable from \(s\), and its vertex \(b\) has an arc to \(t\); both access conditions are needed for this repeated-cycle construction to give walks from \(s\) to \(t\).
Building an All-Pairs Distance Table
In the all-pairs problem, reversing the order of a pair can change the answer because arcs have direction. The diagonal entries are zero when there is no negative closed walk at that vertex; they can be \(-\infty\) if such a walk is reachable from and can return to the vertex. The following small example has positive weights and a directed cycle, so all its pairwise distances are finite.
Worked Example: An All-Pairs Distance Table
Let \(G\) have vertex set \(V=\{p,q,r\}\) and weighted arc set \(p\to q:2,\ q\to r:1,\ p\to r:6,\ r\to p:4\). There are no other arcs. Compute every ordered-pair distance.
From \(p\), the distances are \(d_w(p,p)=0\), \(d_w(p,q)=2\), and \(d_w(p,r)=\min(6,2+1)=3\). From \(q\), the direct route to \(r\) costs \(1\); the route \(q\to r\to p\) costs \(1+4=5\), so \(d_w(q,p)=5\). The empty path gives \(d_w(q,q)=0\). From \(r\), the direct route to \(p\) costs \(4\), and the route \(r\to p\to q\) costs \(4+2=6\), so \(d_w(r,q)=6\); also \(d_w(r,r)=0\).
Thus the table, with row giving the starting vertex and column giving the destination, is:
| From / to | \(p\) | \(q\) | \(r\) |
|---|---|---|---|
| \(p\) | \(0\) | \(2\) | \(3\) |
| \(q\) | \(5\) | \(0\) | \(1\) |
| \(r\) | \(4\) | \(6\) | \(0\) |
Check: the table is not symmetric: \(d_w(p,q)=2\), while \(d_w(q,p)=5\), because the available directed routes differ. For the two entries improved by a multi-arc route, \(d_w(p,r)=2+1=3<6\), and \(d_w(q,p)=1+4=5\). The remaining off-diagonal entries are the direct arcs \(p\to q\), \(q\to r\), and \(r\to p\); their alternatives go around the positive-weight cycle and cost more.
Common Pitfalls and Why the Distinctions Matter
Do not ignore arc direction. In the negative-arc example, the arc is \(b\to a\) with weight \(-3\), not \(a\to b\). A mistaken reversal might claim that the route \(s\to a\to b\) has cost \(4+(-3)=1\), but that route is not directed: there is no arc \(a\to b\). The valid route to \(a\) through \(b\) is \(s\to b\to a\), with cost \(5+(-3)=2\). The direct route \(s\to a\) costs \(4\), so the correct distance is \(2\), not \(1\).
A negative weight is not the same as an unbounded distance. The negative arc \(b\to a\) in that example gives a finite improvement because there is no way to return and repeat a negative closed segment. By contrast, in the negative-cycle example, each traversal of \(a\to b\to a\) reduces the cost by \(2\). Checking whether a negative closed segment can be used on a route from the source to the destination prevents these two situations from being confused.
A shortest walk need not be a path. Paths have no repeated vertices; walks may repeat them. If a zero-cost cycle is inserted into a minimum-cost walk, the resulting walk can still have minimum cost, but it is not a path. When the distance is finite, the theorem guarantees a minimum-cost path without repeated vertices; it does not redefine every minimum-cost walk as a path.
The distinction between single-source and all-pairs questions also affects the amount of information required. A single-source distance list answers questions only for one fixed starting vertex. An all-pairs table records distances for every ordered pair, and it can reveal asymmetry that a single row alone does not show.
Check Your Understanding
Use the definitions of directed walks, paths, and costs to answer these questions.
- In a weighted digraph, what condition distinguishes a directed path from a directed walk?
- For the graph in the first worked example, what is the cost of \(s\to b\to a\to t\), and why is it not the direct route to \(t\)?
- Why does the negative arc in the second worked example not force \(d_w(s,t)=-\infty\)?
- In the third worked example, what happens to the cost of the specified \(s\)-to-\(t\) walk when the negative closed segment is traversed one additional time?
- Why can the all-pairs distances \(d_w(p,q)\) and \(d_w(q,p)\) differ in a digraph?