Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 16 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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