This is the authors' abstract. We don't add key points for this paper.
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.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Goldfarb et al. (1991) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: