Reconstructing shortest paths

This paper develops a polynomial-time algorithm that reconstructs a shortest path between two vertices using only the all pairs shortest path distance matrix. For graphs with positive edge weights, the algorithm requires O(ℝVℝlogℝVℝ) time. When the graph contains both positive and negative, but not zero, edge weights, and all cycles have positive length, the algorithm runs in O(ℝVℝ²) time. The remarkable feature about the algorithm is that it does not require explicit information about edges in the original graph.