« go back to the overview on Stefan's research

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 [1] 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)\).

In a way, both BFS and Dijkstra’s algorithm already fix shortest distances on after the other and basically enumerate partial solutions. With little changes, we get algorithms that enumerate shortest distances with delay in the order of the maximum degree \(\Delta\) of the graph on unweighted and \(O(\Delta + \log(n))\) on graphs with non-negative edge weights: Roughly speaking, whenever BFS (or Dijkstra) fully processed a vertex and iterated over all its neighbors, it can emit the shortest distance to this vertex.

Note that a homogeneous enumeration of the partial solutions would require a delay in the order of the average degree of the graph (not the maximum degree). However, this is not possible, even if the average degree is constant: Consider a graph that roughly consists of a clique of \(k\) vertices and a path of \(k^2\) vertices as shown in the following picture:

No algorithm can reliably distinguish the three different ways, the clique and the path could be connected, without inspecting at least \((k-1)^2\) vertices and/or edges first. Thus, if the source vertex of the SSSP instance lies in the clique, any algorithm needs \(\Omega(k^2)\) steps before being able to correctly determine a distance to any vertex in the path. As there are only \(k\) distances the algorithm can emit before that, this results in an enumeration delay of at least \(\Omega(k)\). This graph has maximum degree \(\Delta = k-1\), thus the delay is in \(\Omega(\Delta)\).

For APSD problems, we can achieve a better delay than the maximum degree: As every vertex has a distance of 0 to itself and every edge corresponds to a distance of 1, there are plenty easy to compute outputs with which an algorithm can gain a head start on the computation of more complicated shortest distances.

We refer to [5] for more results on several variants of both SSSD and APSD including formal proofs of the above statements. Whilst we were able to show a series of upper and lower bounds on the enumeration complexity of shortest distance problems on unweighted graphs and graphs with non-negative edge weights, it remains open whether efficient enumeration is possible at all for graphs with negative edge weights.

1. E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math., vol. 1, no. 1, pp. 269–271, Dec. 1959, 10.1007/BF01386390.
2. S. Warshall, “A Theorem on Boolean Matrices,” J. ACM, vol. 9, no. 1, pp. 11–12, Jan. 1962, 10.1145/321105.321107.
3. R. W. Floyd, “Algorithm 97: Shortest Path,” Communications of the ACM, vol. 5, no. 6, pp. 345-, Jun. 1962, 10.1145/367766.368168.
4. U. Zwick, “Exact and Approximate Distances in Graphs — A Survey,” in Algorithms — ESA 2001, Berlin, Heidelberg, 2001, pp. 33–48. 10.1007/3-540-44676-1_3.
5. K. Casel, T. Friedrich, S. Neubert, and M. L. Schmid, “Shortest Distances as Enumeration Problem,” arXiv:2005.06827 [cs], Feb. 2021, http://arxiv.org/abs/2005.06827