Is there an algorithm for finding the shortest path in an undirected weighted graph?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Shortest Path on an Undirected Graph? might be interesting. $\endgroup$– user2025Commented Sep 20, 2012 at 14:26
-
3$\begingroup$ This question is incredibly thin and answers can be found on Wikipedia as well as in any basic algorithms textbook. Virtual vote to close. $\endgroup$– RaphaelCommented Sep 23, 2012 at 14:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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].
[1] Subcubic Equivalences Between Path, Matrix, and Triangle Problems
answered Sep 20, 2012 at 15:03
-
$\begingroup$ 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. $\endgroup$ Commented Sep 20, 2012 at 16:28
-
$\begingroup$ 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. $\endgroup$ Commented Sep 20, 2012 at 19:25
-
$\begingroup$ @rizwanhudda, I should make clear that optimal in my answer, is with respect to the size/weight of the path, not in runtime. $\endgroup$ Commented Sep 20, 2012 at 20:31
-
$\begingroup$ Having re-read the OP questions, I realize why the confusion arose. I have edited the answer accordingly. $\endgroup$ Commented Sep 22, 2012 at 18:00
-
$\begingroup$ "Shortest" already means "optimal". $\endgroup$– JeffECommented Sep 23, 2012 at 14:06