5
$\begingroup$

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

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

1 Answer 1

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$
6
  • $\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$ 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$ 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$ 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$ Sep 22, 2012 at 18:00
  • $\begingroup$ "Shortest" already means "optimal". $\endgroup$
    – JeffE
    Sep 23, 2012 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.