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?

$\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
    Commented Nov 8, 2022 at 8:41
  • 1
    $\begingroup$ math.stackexchange.com/q/58198/14578 $\endgroup$
    – D.W.
    Commented 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.
    Commented Nov 9, 2022 at 9:37

1 Answer 1

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})$.

$\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.