Timeline for All pairs shortest path with maximum distance
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 25, 2016 at 7:39 | answer | added | Manfred Weis | timeline score: 1 | |
| Feb 24, 2016 at 15:32 | comment | added | Steve Huntsman | en.wikipedia.org/wiki/… | |
| Feb 24, 2016 at 8:46 | comment | added | usul | I'm skeptical that you can find such an algorithm, for the following reason. Suppose the shortest path between A and C is 50, so you don't care if the algorithm finds it. But this path might first go from A to B and then from B to C, and these are both shortest paths of lengths less than 30 (let's say), so you do want the algorithm to find those. So you're only saving yourself the easy work ... even if almost all pairs of nodes have farther distance than your max, it feels like you only could save yourself $O(n^2)$ work off an $O(n^3)$ algorithm. (unless the graph is sparse) | |
| Feb 24, 2016 at 6:01 | answer | added | Manfred Weis | timeline score: 1 | |
| Feb 23, 2016 at 20:28 | comment | added | Rob | OH sorry I did not read the all pairs of nodes.. in that case you want to use Dijkstra's algorithm. You just need to run it with each node as the source node. :) every run will give you the shortest path from the source to every other reachable nodes in the graph. | |
| Feb 23, 2016 at 20:23 | comment | added | Rob | Yes as long as you do not have negative weights on the edges.. If you do just add the value of of the most negative weight to every edge so that all the weights are all positive. | |
| Feb 23, 2016 at 20:20 | history | edited | sdrdis | CC BY-SA 3.0 |
added 4 characters in body
|
| Feb 23, 2016 at 20:20 | comment | added | sdrdis | The graph is not directed. There are weights on my edges. I want to get the distance between all nodes (with a distance between them inferior to a specific number), will A* work efficiently here too ? | |
| Feb 23, 2016 at 19:42 | comment | added | Rob | Do you have a directed graph? Are there weights (distance values) on your edges? A* is a good algorithm to use.. just have it exit early or return nothing if the path discovered it too long. | |
| Feb 23, 2016 at 19:38 | review | First posts | |||
| Feb 23, 2016 at 20:15 | |||||
| Feb 23, 2016 at 19:34 | history | asked | sdrdis | CC BY-SA 3.0 |