Shortest path algorithms using dynamic breadth‐first search

A new O(nm) label‐correcting algorithm is presented for finding shortest paths from a given node to all other nodes in a network of n nodes and m arcs or finding a directed cycle of negative length. In this algorithm, a node is scanned on the k ‐th scanning step only if its “label depth”—i.e., the length of the path corresponding to the distance label—equals k . Variants of this algorithm are discussed, and computational results show that several of these are very efficient. A new criterion for detecting a negative cycle that is also based on the label depth of a node is given, and computational tests show that it is extremely effective.