sssp (optimized)

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Abstract

We give a deterministic \(O(m \log_\frac{2}{3} n)\)-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 \(O(m + n \log n)\) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP.

1. Introduction

In an \(\mathrm{m}\)-edge \(\mathrm{n}\)-vertex directed graph \(G = (V, E)\) with a non-negative weight function \(w : E \rightarrow R \geq 0\), single-source shortest path (SSSP) considers the lengths of the shortest paths from a source vertex s to all$\mathrm{v} \subseteq \mathrm{V} $. Designing faster algorithms for SSSP is one of the most fundamental problems in graph theory, with exciting improvements since the 50s.