# The solution for the all-pair shortest path problem on unweighted and undirected graph

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?

• 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? Commented Nov 8, 2022 at 8:41
• math.stackexchange.com/q/58198/14578
– D.W.
Commented Nov 8, 2022 at 21:38
• The title says "all-pair" but the body says "multi-source". Please edit to make them consistent.
– D.W.
Commented Nov 9, 2022 at 9:37

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