Academic
Publications
All Pairs Shortest Paths in Undirected Graphs with Integer Weights

All Pairs Shortest Paths in Undirected Graphs with Integer Weights,10.1109/SFFCS.1999.814635,Avi Shoshan,Uri Zwick

All Pairs Shortest Paths in Undirected Graphs with Integer Weights   (Citations: 49)
BibTex | RIS | RefWorks Download
We show that the All Pairs Shortest Paths (APSP) problem for undirected graphs with integer edge weights taken from the range can be solved using only a loga- rithmic number of distance products of matrices with ele- ments in the range . As a result, we get an algorithm for the APSP problem in such graphs that runs in time, where is the number of vertices in the input graph, is the largest edge weight in the graph, and is the exponent of matrix multiplication. This improves, and also simplifies, an time algorithm of Galil and Margalit.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: