Timeline for Dijkstra's algorithm to compute shortest paths using k edges?
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 19, 2020 at 19:31 | comment | added | D.W.♦ | cs.stackexchange.com/q/118977/755 | |
| Feb 19, 2016 at 3:07 | history | tweeted | twitter.com/StackCompSci/status/700517045566365696 | ||
| Feb 17, 2016 at 7:25 | comment | added | Raphael | Note that your target running time, assuming the bound is tight, is worse than Bellman-Ford, which runs in time $O(|V| + k \cdot |E|)$ here. | |
| Feb 17, 2016 at 7:20 | comment | added | Raphael | I edited to remove a potential confusing point for readers: Bellman-Ford only requires that the graph have no negative cycles; you want to assume more. | |
| Feb 17, 2016 at 7:18 | history | edited | Raphael | CC BY-SA 3.0 |
edited tags
|
| Feb 17, 2016 at 7:12 | history | edited | Mathguy | CC BY-SA 3.0 |
added 33 characters in body
|
| Feb 17, 2016 at 6:56 | vote | accept | Mathguy | ||
| Feb 17, 2016 at 6:26 | answer | added | D.W.♦ | timeline score: 5 | |
| Feb 17, 2016 at 6:23 | comment | added | D.W.♦ | OK. Please edit the question to include this information, and also present your algorithm. We want questions to be self-contained, so people don't need to read the comments to understand the question. | |
| Feb 17, 2016 at 6:18 | comment | added | Mathguy | @D.W. thanks for the response! 1. No, only >= 0 edge weights. 2. The time complexity I'm looking for is $O(k*(V+E)*log(V))$ and that's the complexity of my algorithm too, but I'm not sure if it's right. Also, please could you link me to the 'product construction' solution? | |
| Feb 17, 2016 at 3:24 | comment | added | D.W.♦ | See also cs.stackexchange.com/a/43099/755 for a loosely related but not identical problem. | |
| Feb 17, 2016 at 3:20 | comment | added | D.W.♦ | 1. Does the graph have any edges with negative length? 2. What time complexity are you looking for? What's the fastest algorithm you were able to come up with? There's a standard solution based on "the product construction" that increases the running time by a factor of $k$; is that of interest to you? | |
| Feb 16, 2016 at 13:04 | comment | added | mewa | As far as I remember you can use Dijkstra's algorithm instead of Bellman-Ford when you don't have edges with negative distance in you graph; I'd have to take a closer look at both the algorithms to elaborate more though | |
| Feb 16, 2016 at 12:13 | review | First posts | |||
| Feb 16, 2016 at 13:15 | |||||
| Feb 16, 2016 at 12:09 | history | asked | Mathguy | CC BY-SA 3.0 |