We investigate the single source shortest distance (SSSD) and all pairs shortest distance (APSD) problems as enumeration problems (on unweighted and integer weighted graphs), meaning that the elements \((u, v, d(u, v))\) – where \(u\) and \(v\) are vertices with shortest distance \(d(u, v)\) – are produced and listed one by one without repetition.
Computing distances and shortest paths in (weighted or unweighted) graphs is one of the most fundamental problems in both theoretical and applied computer science and thus many algorithms are known for different variants of the problems. On a graph with \(n\) vertices and \(m\) edges, the most famous algorithms have the following (total time) runtimes:
- SSSD in unweighted graphs can be computed with a breadth first search (BFS) in \(O(n + m)\) steps, which is optimal.
- With an efficient priority queue, Dijkstra’s algorithm  solves SSSD in graphs with non-negative edge weights with a runtime in \(O(m + n \log (n))\).
- APSD in unweighted graphs can be computed with \(n\) runs of BFS in \(O(n\cdot(n+m))\).
- The algorithm of Floyd-Warshall [2,3] solves APSD in weighted graphs in \(O(n^3)\).