Single-Source Shortest Path

In the Single-Source Shortest Paths (SSSP) problem, we aim to find the shortest paths weights (and the actual paths) from a particular single-source vertex to all other vertices in a directed weighted graph (if such paths exist).

The SSSP problem has several different efficient (polynomial) algorithms:


...that can be used depending on the nature of the input directed weighted graph, i.e. weighted/unweighted, with/without (negative weight) cycle, or structurally special (a tree/a DAG).