Finding all best ties by a K shortest paths method of Dreyfus in a general digraph for routing control
Eiji Mizutani · 2014
For finding all-pairs shortest paths in a digraph of n nodes, the well-known Floyd-Warshall method yields a particular best path between each pair of nodes efficiently in running time O(n3) when there is no negative-cost cycle (and all ties are ignored). Such a digraph may be a model of a real-world transportation, communication, or road network; then, the information of alternative best routing (if any) would be useful for routing control. We thus first ask if there exists any “tie” (i.e., another best path) between each pair of designated nodes; if any tie exists, we then list them all of the same shortest length. To this end, we employ a so-called Dreyfus method (coined by Lawler, 1976), an efficient auxiliary-information dynamic-programming (DP) procedure that can find additional K best paths in O(Knlogn) in addition to a given best path in a single-source shortest-path problem. This paper shows how Dreyfus's DP finds alternative best paths (while detecting a zero-cost cycle if it exists at the same time) efficiently in conjunction with auxiliary functions for evaluating optimal value functions. Its computational convenience has been somewhat overlooked in the literature.