We give a deterministic -time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP.
1. Introduction
In an -edge -vertex directed graph with a non-negative weight function , single-source shortest path (SSSP) considers the lengths of the shortest paths from a source vertex s to all. Designing faster algorithms for SSSP is one of the most fundamental problems in graph theory, with exciting improvements since the 50s.