5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Shortest Path on an Undirected Graph? might be interesting. $\endgroup$ – user2025 Sep 20 '12 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$ – Raphael Sep 23 '12 at 14:10
3
$\begingroup$

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

$\endgroup$
  • $\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$ – rizwanhudda Sep 20 '12 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$ – BlueRaja - Danny Pflughoeft Sep 20 '12 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$ – Nicholas Mancuso Sep 20 '12 at 20:31
  • $\begingroup$ Having re-read the OP questions, I realize why the confusion arose. I have edited the answer accordingly. $\endgroup$ – Nicholas Mancuso Sep 22 '12 at 18:00
  • $\begingroup$ "Shortest" already means "optimal". $\endgroup$ – JeffE Sep 23 '12 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.