Premium
Shortest path algorithms using dynamic breadth‐first search
Author(s) -
Goldfarb Donald,
Hao Jianxiu,
Kai ShengRoan
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210105
Subject(s) - node (physics) , algorithm , shortest path problem , path (computing) , computer science , yen's algorithm , path length , mathematics , k shortest path routing , combinatorics , dijkstra's algorithm , graph , computer network , structural engineering , engineering , programming language
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.