All pairs lightest shortest paths
Uri Zwick · 1999
Two vertices in a weighted directed graph may be connected by many shortest paths. Although all these paths are shortest in terms of weight, the number of edges on them may vary substantially. This leads us to consider the All Pairs Lightest Shortest Paths (APLSP) problem. A solution to this problem is a representation of shortest paths between all of pairs of vertices in the graph such that each of these shortest paths uses a minimal, or a close to minimal, number of edges. We present the following algorithms for obtaining exact or approximate solutions to the APLSP problem: ffl An ~ O(n 2+ ) time algorithm for exactly solving the APLSP problem for directed graphs with integer weights of small absolute value, where n is the number of vertices in the graph and ! 0:747 is the solution of the equation !(1; ; 1) = 3, where !(1; ; 1) is the exponent of the multiplication of an n \\Theta n matrix by an n \\Theta n matrix. ffl An ~ O(n 2+ ) time algorithm, where ! 0:575 is the solutio...