0
$\begingroup$

The multi-source shortest path problem for unweighted and undirected graph is as follows: Given an unweighted and undirected graph, find the length of the shortest path between any pair of vertexes.

A straightforward method is to use BFS starting from each vertex, as the time complexity of BFS is O(V+E), the total time consumption is O(V(V+E)). My problem is: Are there other algorithms for the problem with better time complexity?

Improve this question
$\endgroup$
3
  • $\begingroup$ I assume that you have a designated set of vertices $S \subseteq V$, and you are interested in the minimum distance between pair of vertices in $S$. Can you efficiently check if the distance is 1? If it's not, can you efficiently check if it's 2? Can you generalize for larger distances? $\endgroup$
    – Dmitry
    Nov 8, 2022 at 8:41
  • 1
    $\begingroup$ math.stackexchange.com/q/58198/14578 $\endgroup$
    – D.W. ♦
    Nov 8, 2022 at 21:38
  • $\begingroup$ The title says "all-pair" but the body says "multi-source". Please edit to make them consistent. $\endgroup$
    – D.W. ♦
    Nov 9, 2022 at 9:37

1 Answer 1

Reset to default
2
$\begingroup$

This paper shows how to solve the problem in time $O(n^{\omega} \log n)$, where $\omega < 2.372$ is the matrix multiplication exponent.

This means that you have a better algorithm than repeated BFS when $|E|$ is asymptotically larger than $ \frac{n^{w-1}}{\log n}$, for example when $|E| = \Omega(n^{1.372})$.

Improve this answer
$\endgroup$

Your Answer

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

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