# Finding the Shortest path in undirected weighted graph

Is there an algorithm for finding the shortest path in an undirected weighted graph?

• Shortest Path on an Undirected Graph? might be interesting. – user2025 Sep 20 '12 at 14:26
• This question is incredibly thin and answers can be found on Wikipedia as well as in any basic algorithms textbook. Virtual vote to close. – Raphael Sep 23 '12 at 14:10

Given a graph $G = (V, E)$ find the shortest path between any two nodes $u,v \in V$. It can be solved by Floyd-Warshall's Algorithm in time $O(|V|^3).$ Many believe the APSP problem requires $\Omega(n^3)$ time, but it remains open if there exists algorithms taking $O(n^{3 - \delta} \cdot \text{poly}(\log M))$, where $\delta > 0$ and edge weights are in the range $[-M, M]$.
The reasoning for this is upon close examination we see that the APSP problem can be solved by matrix multiplication. If we replace the operators to $\{\text{min}, +\}$ instead of $\{ +, \cdot \}$ we may use the framework for matrix multiplication to compute the solution. What is interesting is if there exists sub-cubic algorithms for the APSP problem, then there exists sub-cubic algorithms for many related graph and matrix problems [1].