The Bellman-Ford algorithm solves the single-source shortest path problem on directed, weighted graphs in the general case: Edges with negative weights are allowed, if there is no negative cycle reachable from the source vertex s. (With such a cycle there is no shortest path to some vertices reachable from s). The algorithm runs in (nm) time, where n and m are the numbers of vertices and edges respectively. Therefore many improvements have been suggested. One of them is Tarjan's breadth- rst scanning (BFscan) algorithm. The worst-case runtime remains the same, but BFscan performs much better than the Bellman-Ford algorithm in practice. The original BFscan terminates, i there is no negative cycle reachable from the source vertex. Otherwise the method never halts. In order to make BFscan robust, a few distinct supplements have been proposed. In this paper we introduce a new completion, and compare it with those known to us.
Given a network represented by a directed graph with possibly negative edge weights, nding shortest paths
from a source vertex s to the other vertices is a basic problem [
In the next section we enumerate his results up to his breadth- rst scanning algorithm. Then, in section 3, we introduce our re nement which is a new check for negative cycles, and compare it with some previous proposals.
In this section we introduce rst the basic notions, and the formal problem. Next we give an initial solution,
and then re ne it, following Tarjan [
The problem Let G = (V; E) be a directed graph, where jV j = n > 0; jEj = m 2 0::n2, length : E ! R (possibly negative), E
V V; s 2 V .
De nition 2.1. p =< v0; : : : ; vk > (k length(p) = Pk
i=1 length(vi i; vi), Path p is a cycle, i k > 0 ^ v0 = vk.
0) is a path2, i fv0; : : : ; vkg e(p) = k.
Cycle p is negative, i length(p) < 0.
V , and f(vi i; vi)ji 2 1::kg
E.
De nition 2.2. Let s; t 2 V ; t is reachable form s, i there is some path from s to t, i.e. there is a < v0; : : : ; vk > (k 0) path so that v0 = s ^ vk = t Problem 2.3. An important network optimization problem is the single source problem: Given a source s 2 V , nd a shortest path from s to v for each v 2 V reachable from s.
Any other shortest path nding problem can be reduced to this one [
In this paper we develop an algorithm which computes a shortest-path tree or detects a negative cycle reachable from s. In the latter case, clearly there is no solution.
If the algorithm computes a shortest-path tree, then for each reachable vertex v 6= s, label p(v) shows its parent in the tree and d(v) shows the distance (i.e. the length of the optimal path from s to v); p(s) = N IL, d(s) = 0; and for any non-reachable vertex u, p(u) = N IL, d(u) = 1. 2.2
Ford's labeling method This algorithm initializes each vertex as if non-reachable, except that d(s) = 0. Later it maintains a tree rooted at s which approximates step-by-step the result. After the previous initialization, it repeats the labeling step while it is applicable:
Lemma 2.5. The labeling method maintains the invariant that if d(v) < 1, there is a path form s to v of length d(v). (Proof: by induction on the number of labeling steps.) Theorem 2.6. When the labeling method halts, d(v) is the length of a shortest path from s to v, if v is reachable from s, and d(v) = 1 otherwise. If there is a negative cycle reachable from s, the method never halts. (Proof: Let p be some path from s to v. When the labeling method halts, length(p) d(v) by induction on e(p) (see De nition 2.1). Now with Lemma 2.5, d(v) is the length of a shortest path from s to v. If v is not reachable from s, d(v) = 1 with the same lemma. If there is a negative cycle reachable from s, consider some element t of this cycle. Now { with Theorem 2.4 { there is no shortest path from s to t, but if the method halted, d(t) would be the length of a shortest path from s to t, which proves that the method never halts.) Lemma 2.7. If at some time during the labeling method pk(v) = v for some v 2 V and k positive integer, then the corresponding cycle in G is negative.
The previous lemma helps us to identify negative cycles [
Theorem 2.8. When the labeling method halts, the parent pointers de ne a shortest-path tree for the subgraph of G induced by the vertices reachable from s.
If no negative cycle is reachable from s, Ford's method halts, but it may be exponential in m [
Our algorithm, and each known algorithm which solves the single source problem (Problem 2.3) is a special case of Ford's labeling method, except that they may add various halting conditions in order to handle the case when this algorithm goes into in nite loop (i.e. there is a negative cycle reachable from s). 2.3
The labeling and scanning method
Tarjan's rst re nement is the labeling and scanning method [
With the usual initialization, s becomes labeled, and any other vertex unlabeled. Then we repeat the scanning step while there is any labeled vertex.
SCANNING STEP: Select a labeled vertex v and scan it, thereby converting it to the scanned state, by applying the labeling step to each edge (v; w) such that d(v) + length(v; w) < d(w), thereby converting w to the labeled state.
The following invariant [
Lemma 2.9. In the labeling and scanning method, if d(v) + length(v; w) < d(w), then v is in the labeled state. 2.4
The breadth- rst scanning method
E cient scanning orders (like topological scanning, and Dijkstra's algorithm [
d(u):= INFTY; p(u):= NIL; state(u):= unlabeled d(s) := 0; queue Q := [s]; state(s) := labeled; while( Q \= [] ) u := deQueue(Q); state(u) := scanned; for each v : (u,v) in E if d(u)+length(u,v) < d(v) d(v) := d(u)+length(u,v); p(v) := u; if state(v) \= labeled
enQueue(Q,v); state(v) := labeled
Because procedure BFscan is a special case of the labeling method, Theorem 2.6 and 2.8 imply that, if BFscan
halts, then it computes the shortest-path tree with the appropriate d(v) distance values and p(v) parent pointers.
Form Theorem 2.6 we know that if there is a negative cycle reachable from s, BFscan never halts. The following
theorem makes sure that otherwise it stops in O(nm) time. First we divide its execution into passes [
In order to make BFscan robust, one must ensure that it halts even if there is a negative cycle reachable form
s. Tarjan [
Now we give another, stronger condition based on our new e(v) attribute of the labeled and scanned vertices. With this condition, our algorithm never stops later, and sometimes earlier then Tarjan's pass counting BFscan.
We introduce our new label e(v) of the vertices into BFscan. It counts the number of edges on the shortest (i.e. lightest or cheapest) path found to vertex v (see De nition 2.1). We prove, that if e(v) n, then among the ancestors of v we can nd a cycle, and this is a negative cycle reachable from s. And if there is a negative cycle reachable from s, then we nd e(v) n before the end of pass n 1. Based on this, we extend BFscan with the necessary check, as it is shown in Figure 1. Our CBFscan function returns NIL, if it computes the shortest-path tree. If it recognizes that for some v 2 V , e(v) n, it returns v. Then it is easy to nd a negative cycle among the ancestors of v in (n) time. (See Figure 2.) vertex function CBFscan( vertices V, edges E, vertex s ) 1: for each u in V 2: d(u) := INFTY; p(u) := NIL; state(u) := unlabeled 3: d(s) := 0; e(s) := 0 4: queue Q := [s]; state(s) := labeled 5: while( Q \= [] ) 6: u := deQueue(Q); state(u) := scanned 7: for each v : (u,v) in E 8: if( d(u)+length(u,v) < d(v) ) 9: d(v) := d(u)+length(u,v) 10: p(v) := u; e(v) := e(u)+1 11: if( e(v) < n ) 12: if state(v) \= labeled 13: enQueue(Q,v); state(v) := labeled 14: else return v // Neg.cycle among ancestors of v 15: return NIL // Shortest-path tree computed
Lemma 3.1. Let P (w) be the following assertion: the path q(w) = [pe(w)(w); pe(w) 1(w); : : : ; p(w); w] exists and (8x 2 q(w))(d(x) < 1 and x is reachable from s). Thus the while loop of function CBFscan at line 5 maintains the following invariant I5: for each vertex w, if state(w) = labeled then n > e(w) 0 ^ P (w). Also at line 11 we have the invariant I11: I5 ^ n > e(u) 0 ^ P (u) ^ n e(v) 0 ^ P (v). Proof. First I5 is clearly true because only s is labeled, Q = [s] (in general Q contains the labeled vertices), and e(s) = 0 ^ d(s) = 0 ^ q(s) = [s].
Supposing that at line 5 I5 is true, there are too cases. (I) If From line 5 the program goes directly to line 11, I11 will also be true. Only the existence of q(v) is nontrivial: If v 2= q(u) then q(v) = q(u) concatenated with [v]. If v 2 q(u) then for some k 2 1::e(v); v = pk(v); so we have found a cycle, and q(v) exists. (II) If From line 5 the program goes to line 5 without touching line 11, I5 remains clearly true for the remaining labelled vertices.
Provided that at line 11 I11 ^ e(v) < n, there are two cases again. (1) From line 11 we go to line 11 without touching line 5, and with the new Q and v I11 remains true. (2) From line 11 we go to line 5 without touching line 11, and with the new Q I5 will be true.
Consequently both of I5 and I11 are invariants.
Theorem 3.2. If in the test in line 11, e(v) n is found, then we can nd a cycle following the parent pointers of v; this cycle is negative, and reachable form s.
Proof. I11 ^ e(v) n implies e(v) = n. Thus the number of the nodes on the path q(v) is n + 1, and so (9i; j 2 0::n)(i > j ^ pi(v) = pj (v)). Lemma 2.7 and I11 imply that the cycle [pi(v); : : : ; pj (v))] is negative, and reachable form s.
Lemma 3.3. If CBFscan is in pass j, for each labeled vertex u (to be) scanned in this pass, e(u) each labeled vertex v to be scanned in the next pass, e(v) > j. j, and for Proof. Only s is scanned in pass 0, and e(s) = 0. For each successor v of s, e(v) = 1 and v is scanned in pass 1. Then the lemma comes by induction on the number of passes: Let us suppose that we are in pass j, and the invariant of this lemma stands. The new e(v) values are generated in line 10, with the statement e(v) := e(u) + 1, where u is a vertex being scanned in pass j, and so e(u) j. Thus e(v) j + 1, and this ts the invariant, regardless of whether v is a vertex to be scanned yet in pass j or only in pass j + 1.
Theorem 3.4. If no negative cycle is reachable form s, the run of CBFscan follows the run of BFscan. If a negative cycle is reachable from s, then CBFscan at line 11 nds a vertex v with e(v) = n. In any case, CBFscan halts at the latest during pass n 1, and runs in O(nm) time.
Proof. If there is no negative cycle reachable form s, Theorem 3.2 implies that the test in line 11 always nds e(v) < n, the run of CBFscan follows the run of BFscan, and with Theorem 2.11 CBFscan also stops by the end of pass n 1.
If a negative cycle is reachable from s, Theorem 2.11 makes sure that BFscan performs its pass n 1, n, and so on, in nitely. While CBFscan in line 11 nds e(v) < n, the run of CBFscan follows the run of BFscan. This means that if CBFscan halts, it halts because at the test in line 11 e(v) n, and considering I11 in Lemma 3.1, it stops with e(v) = n. If CBFscan does not halt by the end of its rst n 2 pass, it halts during its pass n 1: Considering Lemma 3.3 we have that each labeled vertex u being scanned in this pass has e(u) n 1. We can suppose that during pass n 1 CBFscan goes at least once to the test in line 11. (Otherwise at the end of pass n 1 CBFscan would nd Q = [] at line 5, and it would run and stop following BFscan, but BFscan does not halt in this case.) At line 11, e(u) n 1. Consequently e(v) n. Then CBFscan halts.
Regardless of whether a negative cycle is reachable from s or not, CBFScan stops by the end of pass n 1.
Thus its total runtime is O(nm). (Each pass requires O(m) time, since in a pass maximum m edges are processed,
in pass 0 only s is scanned, and from pass 1, during a pass (i) each vertex is scanned at most once and (ii) not
more than min(n; m) vertices are scanned [
Comparing our check for negative cycles and previous proposals If there is no negative cycle reachable from s, we have seen that both of Tarjan's pass counting BFscan, and our CBFscan follows the run of BFscan, and they stop at the same point with Q = []. If a negative cycle is reachable from s, Tarjan's pass counting BFscan stops at the end of pass n 1, while our CBFscan halts at the latest during pass n 1. However, the reader can check, that for example on the graph shown at Figure 3, CBFscan halts by the end of the rst pass.
And it is easy to create similar graphs of any size so that CBFscan recognizes the negative cycle, and halts by the end of the rst pass (e.g. let the vertices be fa0; a1; a2; : : : ang where s = a0, length(ai 1; ai) = 0 (i = 1::n), length(a0; aj ) = 1 (j = 2::n)), and length(an; ak) = 1 for some k 2 [0::(n 1)]). s 1 a1 1 3 a2
4 -3 1 a3
can is guaranteed to halt by the end of pass 3, but
{ supposing that the vertices at a scanning step are
put into Q in the order of the indexes { it
recognizes a negative cycle and stops while scanning the
last vertex of pass 1.
Weiss (1995) gives a weaker condition: "by stopping the algorithm3 after any vertex has dequeued jV j + 1 times4,
we can guarantee termination."[
When any vertex v is enqueued nth time, we are at least in pass n 1, because a vertex is enqueued at most once in a pass. In addition, this v will be still in the queue at the end of pass n 1, and Theorem 2.11 implies that there is a reachable negative cycle. Thus it seems to be possible that WiBFscan nds the negative cycle earlier than the pass counting BFscan of Tarjan. But a vertex may not be enqueued in each pass.5 So this algorithm may nd the negative cycle later than Tarjan's version. Surely WiBFscan does not nd the negative cycle earlier than our CBFscan, because in our algorithm, provided that vertex v is labeled during pass n 1, e(v) n, and our algorithm halts, if not earlier.
Let us note, that in the implementation of WiBFscan, for each vertex v we can use a counter of enqueuing events en(v). We suggest that one should initialize en(s) to n 1 immediately before the main loop of WiBFscan, because the rst enqueuing of s in the main loop already shows a negative cycle. Thus the early recognition of a negative cycle going through the start vertex becomes possible without extra cost (although this is a only a special case). 3.2
An open question
Tarjan proposed another, more complex robust version of BFscan which stops "as soon as the parent pointers
de ne a cycle" [
It is clear that if there is no reachable negative cycle, in practice this complex robust BFscan is slower then the other (robust) versions of the BFscan program considered here, because of its complex check.
If there is reachable negative cycle, it usually performs less number of scanning steps than the previously examined robust versions of BFscan because it stops "as soon as the parent pointers de ne a cycle", but still there is no comparison between the practical runtime of this complex robust BFscan and that of CBFscan. 4
If there is no negative cycle reachable from s, the runtime of our CBFscan program, and that of the other robust BFscan versions detailed here are practically the same. In this case Tarjan's more complex robust algorithm (considered in Subsection 3.2) is slower than the other programs.
Otherwise CBFscan nds a negative cycle at last during pass n 1. Tarjan's pass counting BFscan nds it only after pass n 1. Weiss's original version is the weakest because it nds it only in the nth pass or later. Our 3BFscan 4n + 1 times 5We believe, the vertices probably are not enqueued in each pass. improved version WiBFscan nds it sooner or later than Tarjan's pass counting BFscan, but not sooner than our CBFscan (except that with our trick a negative cycle through s is found as soon as in BFscan it is possible). There are cases, when CBFscan nds a negative cycle reachable from s even before pass n faster than the other simple versions of robust BFscan. If there is a negative cycle reachable form s, Tarjan's more complex robust algorithm (see Subsection 3.2) performs the minimal number of scanning steps, but still we have no comparison of the practical runtime of this algorithm and that of CBFscan in this case.