Timeline for Finding the Shortest path in undirected weighted graph
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2012 at 4:19 | vote | accept | rajesh | ||
| Sep 27, 2012 at 4:19 | |||||
| Sep 23, 2012 at 15:31 | comment | added | Nicholas Mancuso | Ok, under your edit yes. I wasn't sure if the OP wanted optimal-time algorithm that gives (implied optimal) solution, or just an algorithm to give the optimal solution. | |
| Sep 23, 2012 at 14:06 | comment | added | JeffE | "Shortest" already means "optimal". | |
| Sep 22, 2012 at 18:00 | comment | added | Nicholas Mancuso | Having re-read the OP questions, I realize why the confusion arose. I have edited the answer accordingly. | |
| Sep 22, 2012 at 18:00 | history | edited | Nicholas Mancuso | CC BY-SA 3.0 |
re-read question.
|
| Sep 20, 2012 at 20:58 | history | edited | Nicholas Mancuso | CC BY-SA 3.0 |
deleted 10 characters in body
|
| Sep 20, 2012 at 20:31 | comment | added | Nicholas Mancuso | @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 19:25 | comment | added | BlueRaja - Danny Pflughoeft | 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 16:28 | comment | added | rizwanhudda | 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 15:16 | history | edited | Nicholas Mancuso | CC BY-SA 3.0 |
formatting.
|
| Sep 20, 2012 at 15:03 | history | answered | Nicholas Mancuso | CC BY-SA 3.0 |