25
$\begingroup$

In an unweighted, undirected graph with $V$ vertices and $E$ edges such that $2V \gt E$, what is the fastest way to find all shortest paths in a graph? Can it be done in faster than Floyd-Warshall which is $O(V^3)$ but very fast per iteration?

How about if the graph is weighted?

$\endgroup$
1
  • $\begingroup$ Note that a graph with $2V>E$ will be severely disconnected. A random graph with so few edges won't even have a giant component. Is this question meant to address such a severely skewed case? $\endgroup$
    – Szabolcs
    Jan 18, 2023 at 12:28

3 Answers 3

35
$\begingroup$

Since this is an unweighted graph, you could run a Breadth First Search (BFS) from every vertex $v$ in the graph. Each run of BFS gives you the shortest distances (and paths) from the starting vertex to every other vertex. Time complexity for one BFS is $O(V + E) = O(V)$ since $E = O(V)$ in your sparse graph. Running it $V$ times gives you a $O(V^2)$ time complexity.

For a weighted directed graph, the Johnson's algorithm as suggested by Yuval is the fastest for sparse graphs. It takes $O(V^2\log V + VE)$ which in your case turns out to be $O(V^2\log V)$. For a weighted undirected graph, you could either run Dijkstra's algorithm from each node, or replace each undirected edge with two opposite directed edges and run the Johnson's algorithm. Both these will give the same aysmptotic times as Johnson's algorithm above for your sparse case. Also note that the BFS approach I mention above works for both directed and undirected graphs.

$\endgroup$
2
  • $\begingroup$ This answer is misleading, as all Johnson's algorithm does is pre-process the graph to enable the use of Dijkstra's algorithm when negative edge weights are present. The suggestion to treat an undirected graph as directed with reciprocal edges and use Johnson's instead of Dijkstra's is not sensible. $\endgroup$
    – Szabolcs
    Jan 18, 2023 at 12:19
  • $\begingroup$ To be fair, the naming of these algorithms in the literature is not quite consistent. The Wikipedia page you link to on "Johnson's algorithm" discusses specifically negative weights. In the same paper where Johnson describes this, he also discusses efficient implementations of Dijkstra's basic idea using a priority queue implemented as a binary heap. This is probably the most common type of implementation you'll find today, and is usually plainly referred to as "Dijkstra's algorithm". $\endgroup$
    – Szabolcs
    Jan 18, 2023 at 13:11
8
$\begingroup$

You can try to make a version of Floyd-Warshall that is faster on sparse matrices.

First, let us recall what this algorithm does:

Let $M$ be a matrix of distances. At the beginning of the algorithm $M_{i,j}$ is the weight of the edge $i \rightarrow j$. If this edge does not exist then $M_{i,j}=\infty$.

The algorithm has $V$ steps. In step $k$ of the algorithm, for every pair of nodes $i,j$ we set

$$M_{i,j} \leftarrow \min\{M_{i,j}, M_{i,k}+M_{k,j}\}.$$

Clearly if $M_{i,k}=\infty$ or $M_{k,j}=\infty$ then no update needs to be performed. Thus, in the first steps of the algorithm, we only need to perform roughly $deg_{in}(k) \cdot deg_{out}(k)$ comparisons where $deg_{in}(k)$ and $deg_{out}(k)$ denote the number of incoming and outgoing edges of the $k$-th node respectively. As the algorithm progresses, more and more entries of the matrix $M$ are filled. Hence, the last steps might take much longer.

Note that we need an efficient way to iterate only over non-infinite cells in the $k$-th row and column of the matrix. This can be done by keeping a set of incoming and outgoing edges for every node.

It appears that the first steps of the algorithm can greatly benefit from sparsity. For example, a randomly constructed graph with $E=O(V)$ suggests that the first iteration ($k=0$) is only $O(1)$ steps. If the graph is split into many connected components then the matrix $M$ would remain relatively sparse throughout the algorithm and the total runtime could be as low as $O(V)$. On the other hand, if the graph contains just one connected component, then the last iteration $k=|V|$ is expected to take $O(V^2)$ steps. In this case the total run-time could be $O(V^3)$. As large as the non-sparse version.

$\endgroup$
6
$\begingroup$

There is Johnson's algorithm, whose running time is $O(V^2\log V + VE)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.