Routines Dijkstra_scan and Plain_sc

Routines Dijkstra_scan and Plain_scan acquire an additional parameter E , thus getting the edge set to scan via this parameter, instead of using the globally defined set E .The call to Dijkstra_scan, in the do < > until loop, is replaced by two consequent calls: Dijkstra_scan(E E −) andPlain_scan(E−).Theorem 5.1. The BFD-r version of BFD is correct, keeping the round number bounds of Theorem 3.4, whichever implementation of Dijkstra on a graph with non-negative edge costs is used in Dijkstra_scan.Proof. Let us show that the proof of Lemma 3.2 (and thus of Proposition 3.3 and Theorem 3.4) remains valid for BFD-r. Itis easy to check that the proof part analyzing the insertion of vertices in P˜ into S remains fully valid, being now relatedto the execution of Dijkstra_scan(E E−). Consider now the concluding remark on ensuring the equality d(v) = opt(v) via executing Relax(vq, v) after inserting vq into S . It remains valid either by executing it in Dijkstra_scan, if c(vq, v) ≥ 0, or by executing it in Plain_scan(E−), otherwise. ❑2.An anonymous referee suggested an observation leading to an improvement of BFD-r and of Theorems 3.4 and 5.1. Let us change BFD-r to BFD-rs as follows. At a preliminary phase, BFD-rs checks whether there exists a cycle in graph (V , E −). If so, it reports on existence of a negative cycle in G . Otherwise, it computes a topological ordering in graph (V , E −). BFD-rs specifies that executions of Plain_scan traverse the edges in E− in the topological ordering of their initial vertices.Let us define negs(P) ≤ neg(P) as the number of intervals of consecutive negative edges in P , excluding the first edge of Pand the interval including the last edge of P , if any; we define negs(G) ≤ neg(G) accordingly.Theorem 5.2. If there is no negative cycle reachable from s in G, BFD-rs correctly computes the shortest path value for all v V and the shortest paths tree in at most negs(G) 2 rounds, whichever implementation of Dijkstra on a graph with non-negative edge costs is used in Dijkstra_scan. Otherwise, it reports the existence of such a cycle. Its running time is as that of BFD.Proof. After a minor change to Lemma 3.2, as follows, the proof of Theorem 5.1 works. In Lemma 3.2, path P˜ ends either before the last edge of P , if non-negative, or before the last interval of consecutive negative edges, otherwise. The discussion of the concluding remark in the proof of Theorem 5.1 remains valid due to the scanning the negative edges by Plain_scan in topological order. ❑Note that the updated measure negs(G) extends the application area of BFD and its modifications to graphs with sparsely distributed clusters of negative edges.3.Let us consider the Dijkstra-like algorithm and its implementation suggested by Dinitz in [8] and adjust BFD-r to using it. The algorithm of [8] works when edge costs are positive real numbers. It generalizes Dijkstra by relaxing its choice condition of the next vertex to scan: from d(v) being minimal in V S to ⎝d(v)/cmin] being minimal in V S , where cmin is the minimal edge cost. Similarly to Dial’s implementation, it uses buckets, but with key ⎝d(v)/cmin]. In contrast to Dial’s implementation, its running time bound is scalable w.r.t. edge costs: O(|E| + max{opt(v)}+cmax ).Let us describe yet another version BFD-r+. Let E+ be the set of edges with positive costs in G , and cm+in be the min- imal positive edge cost (that is, it is cmin of graph (V , E+, c)). BFD-r+ differs from BFD-r in that the two calls replacing Dijkstra_scan are: Dijkstra_ scan (E+) and Plain_scan (E E+).Accordingly, we change the measure of the BFD complexity: Let non_pos(G) be defined similarly to neg(G), but withrespect to edges with non-positive costs.