Per48edjes/dijkstras_discussion.md

## dijkstras_discussion.md

      
    Raw
  

              dijkstras_discussion.md
            
          
    TL;DR: Dijkstra's alone isn't sufficient to solve the all-pairs shortest paths problem, but on an undirected graph, you're right that there is information contained about some of the pairwise shortest paths (i.e., those involving the source vertex as the source or the destination). Depending on the queries (if you know them ahead of time and they were sufficiently contained in a small subgraph), perhaps, you could run Dijkstra fewer than $|V|$ times to answer them.

Hmmmm... I'm don't think Dijkstra alone would give you all-pairs shortest paths (APSPs) among all vertices inside the envelope[1] as it proceeds (or even at the end). The distance estimates are from a single, source vertex $s$, so in an undirected graph you could get some of the pairwise shortest paths, namely, those involving $s$ (e.g., $d(s, v) = d(v, s)$ for any $v$ in the envelope), but not all of them. Maybe you could get away with it if you knew all the pairs you cared about involved $s$?
Johnson's is an APSP algorithm, and the only other ones I can claim to "know" are:

running Bellman-Ford $|V|$ times, which is $O(|V|^{4})$ in the worst case
Floyd-Warshall, which is $O(|V|^{3})$


Johnson's is basically:

Create a "super node" $x$ connected to every vertex in your graph $G$ by an edge of $0$-weight.
Run Bellman-Ford (BF) once from this "super node": (1) to detect negative-weight cycles (if any exists, exit early) and (2) the distances $d(x,v)$ computed by (BF) are the potentials $h(v)$ you use to reweight $G$ so all edges are nonnegative, giving transformed graph $G^{\prime}$.
Run Dijkstra from every vertex in $G^{\prime}$. This will give you APSP in $G^{\prime}$, i.e., $\delta^{\prime}(u, v)$ for all $u, v \in V^{\prime}$.
Recover APSP in $G$ by reversing the reweighting you did above: $\delta(u, v) =  \delta^{\prime}(u, v) - h(u) + h(v)$.

Theoretically (using Fibonacci heaps, which I know literally nothing about other than the runtimes of the operations it supports ad that the constant factors can be so big that, in practice, it doesn't make sense to use them 🙊), Johnson's runtime is $O(|V|^{2} \log |V| + |V||E|)$. Of course, if you use a min-heap, this becomes $O(|V||E| \log |V| + |V||E|)$, which on dense graphs, Floyd-Warshall is probably a better choice.
Johnson's runtime is contingent on your choice of priority queue (similar to Dijkstra...because you're essentially just running Dijkstra $|V|$ times), but on sparse graphs (i.e., $|E| = O(|V|)$ ) it's definitely better than the other two alternatives I mentioned above.

NB: I'm far from an expert on any of this stuff, so please do weigh in if you've anything to add!
[1]: A vertex $v$ is "in the envelope" iff it has a distance estimate, $d(s, v)$, from a source vertex, $s$, that equals the actual shortest path distance $\delta(s, v)$ from $s$ to $v$, i.e., when no other edge relaxation would lower $d(s, v)$. This is equivalent to saying there does not exist a vertex $u$ outside of the envelope such that $d(s,u) + w(u, v) &lt; d(s, v)$.