For a graph G which is not strongly

For a graph G which is not strongly connected, let us generalize the above bound to the following bound BSC C (G) for neg(G), which can be computed by a linear time preprocessing. We begin with computing DAG GSC C of the strongly connected components (SCCs) of G (e.g., by the Kosaraju–Sharir algorithm); the edge between two SCCs is called negative if there exists a negative edge between their vertices in G . We give to each SCC C weight #neg(G(C )), where G(C) is the sub-graph induced by C . We define the weight of a path in GSC C to be the sum of the weights of its vertices plus the number of negative edges in it. We compute the maximal weight of a path from the SCC of s in GSC C (it is well known how to do this using a topological sort). We denote that weight by BSC C (G). It is easy to see that neg(G) BSC C (G), thus implying:Corollary 3.8. For any graph G, the value of BSC C (G) can be computed in a linear time. Then, the stopping condition < i = |V | − 1 >of BFD may be replaced by < i = BSC C (G) + 2 >.Comment: The results of this subsection are slightly improved in part 2 of Section 5.4.Robustness of BFD to implementations of BF1.In practice, it may be reasonable to check the existence of a negative cycle during the BF run, and stop if one is detected. One such checking method is “subtree disassembly” [17] (see also [3]). Any time when Relax(u, v) decreases the value of d(v), subtree disassembly traverses the subtree of the back-pointers tree rooted at v , looking for u. During this traversal, it removes all vertices x v in this subtree, by setting π(x) nil, as if x has not been reached yet. Note that any such removed vertex x currently has a non-optimal value of d(x) > opt(x).Let us show that the basic version of subtree disassembly may be incorporated into BFD as it is. Removal of back-pointers is safe for BFD, since Dijkstra_scan does not depend on back-pointers. Removal of certain vertices from the consideration (which fastens BF in practice) might be unsafe for the correctness of BFD, in general. Pay attention that the correctness of all results of Section 3 is based on Lemma 3.2. The proof of that lemma deals with scanning of vertices x with the optimal values of d(x) opt(x) only. Therefore, removal of vertices with non-optimal values of d(x) made by subtree disassembly does not contradict the correctness of Lemma 3.2, and thus of all the results of Section 3.The additional property of the advanced versions of subtree disassembly and of other negative cycle detecting methods considered in [3] is that they change the order of scanning vertices “on-fly”, using concrete states of the execution of the used negative cycle detecting method. Since the arising scanning order ought not to be by non-decreasing values of d, thus contradicting Dijkstra_scan, they are incompatible with BFD.2.The following basic speedup modification is widely used in practical implementations of BF. It groups Relax(u, v) executions to bunches with the same vertex u, called “scanning u”. When scanning u, it stores the value of d(u). At each round of BF, not all vertices are scanned. Scanning of vertex u is skipped if its current d value equals its d value stored at the last time (in such a case, scanning u is useless). Although the worst case bound of this modification is the same as that of the basic BF, it is known that in practice, this modification significantly decreases the running time.Since grouping Relax’s as above is built-in in Dijkstra_ scan, it is straightforward to modify Dijkstra_scan and BFD accord- ingly. Since each skipped vertex scanning causes no change in the data, each round of the BFD modified as above produces the same result as that of the basic BFD. Therefore, all the correctness and running time statements proved for BFD remain valid for this modified version. However, the advanced versions of the considered modification changing the order of scanning vertices (see e.g., [3]) are incompatible with BFD, in general, by the reason as in part 1 of this section.5.Adjusting BFD to variants of DijkstraLet us study how certain implementations and variants of Dijkstra may be used for implementing a BFD round in order to accelerate it. Accordingly, the factor E V log V in the time bound of Theorem 3.5 could be changed to the time bounds of those implementations/variants.1.Note that some implementations of Dijkstra rely on non-negativity of edge costs, either explicitly or implicitly, and hence might work improperly if there are negative edges in G . In particular, those are implementations using monotone priority queues (see, e.g., [4]). For example, consider the basic Dial’s implementation [7] (see also [20,8], reinventing it). It uses