# 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, 2012 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, 2012 at 14:10

## All-Pairs-Shortest Path

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].

• The Dijkstra's and Bellman Ford's are best known algorithms for graphs with Non-negative and negative edge weights respectively. But, has any one proved a non-trivial lower bound for these problems which matches the best known upper bound? If not, then these are not optimal. Sep 20, 2012 at 16:28
• You should also mention A*, which solves the same problem as Djikstra's but much faster, if you have a decent distance-heuristic available to you. Sep 20, 2012 at 19:25
• @rizwanhudda, I should make clear that optimal in my answer, is with respect to the size/weight of the path, not in runtime. Sep 20, 2012 at 20:31
• Having re-read the OP questions, I realize why the confusion arose. I have edited the answer accordingly. Sep 22, 2012 at 18:00
• "Shortest" already means "optimal". Sep 23, 2012 at 14:06