Exact Shortest Paths with Rational Weights on the Word RAM
Adam Karczmarz, Wojciech Nadara, Marek Sokołowski · Society for Industrial and Applied Mathematics eBooks · 2024
Exact computation of shortest paths in weighted graphs has been traditionally studied in one of two settings. First, one can assume that the edge weights are real numbers and all the performed operations on reals (typically comparisons and additions) take constant time. Classical Dijkstra's and Bellman-Ford algorithms have been described in this setting.