Shortest‐path methods: Complexity, interrelations and new propositions

Abstract We present a new unified approach for shortest‐path problems. Based on this approach, we develop a computational method which consists of determining shortest paths on a finite sequence of partial graphs defined as the “growth of the original graph.” We show that the proposed method allows us to interpret within the same framework several different well‐known algorithms, such as those of D′Esopo‐Pape, Dijkstra, and Dial, and leads to a uniform analysis of their computational complexity. We also stress the existing parallelism between the proposed method and the matrix‐multiplication methods of Floyd‐Warshall, and Dantzig.