SSSP

Single-Source Shortest Path (SSSP) is a fundamental problem in graph theory. Given a weighted graph G = (V, E) and a designated source vertex s ∈ V, the goal is to determine the length of the shortest path from s to every vertex v ∈ V and often to reconstruct those paths. The computed values form a distance function dist(v) and, optionally, a predecessor function to recover the actual paths. Distances assume that the sum of edge weights along a path is the path length; in directed graphs, the problem is defined similarly with respect to edge direction.

When all edge weights are nonnegative, Dijkstra’s algorithm efficiently computes SSSP from s. Using a priority queue, Dijkstra runs in roughly O((V + E) log V) time, with specialized implementations achieving close to O(E log V). For graphs with negative edge weights, Bellman-Ford is used; it computes distances in O(VE) time and can detect negative-weight cycles reachable from s, in which case finite SSSP distances do not exist. In unweighted graphs, BFS yields the SSSP due to unit edge lengths, in linear time O(V + E). SPFA (shortest path faster algorithm) offers a practical alternative for sparse graphs with negative edges, often faster on real-world instances but with less favorable worst-case guarantees.

The output typically includes dist[] (and sometimes pred[] to reconstruct paths) and may be expressed as a shortest-path tree rooted at s. SSSP is a core subroutine in routing protocols, geographic information systems, and various higher-level graph algorithms, including repeated calls to obtain all-pairs shortest paths or to support dynamic graph analyses. Variants exist for dynamic graphs, approximate solutions, and specialized graph classes.