Timeline for C++ Dijkstra's shortest path implementation
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 5, 2017 at 12:54 | vote | accept | HenrikS | ||
| Aug 4, 2017 at 22:15 | comment | added | Loki Astari | There are three things you need to do. 1) Stop using an intrusive algorithm (one that modifies the graph). This is causing most of the issues in your underlying algorithm and only allowing you one cost per node. 2) Use a priority queue that stores {node, cost} in each node and sorted by cost. So you don't need to rebuild the priority queue all the time (you need (1) first) 3) Add an already Visited list (or check completed) before you add children to the end of the frontier. Nice optimization. | |
| Aug 4, 2017 at 22:10 | comment | added | Loki Astari |
I know. As I try and describe below this is because you have not implemented dijkstra correctly. You need to store the distance and node as a pair in the frontier list. Then you don't need to re-sort when you have a shorter distance. When you find a new route to a node you store node and distance as a pair {node, cost} and add that to the frontier list (sorted by distance in the pair). This will then be sorted into the correct place in the priority queue.
|
|
| Aug 4, 2017 at 19:32 | comment | added | HenrikS | @LokiAstari Well I know and I really don't like calling it so often, but I need to resort the queue when I find a shorter path to a node | |
| Aug 4, 2017 at 19:10 | comment | added | Loki Astari |
I think you will find that your code is much more inefficient than priority queue as you are using make_heap in a very inefficient way. You are only supposed to call make_heap() once. Then you are supposed to use push_heap() to add more items. By calling make_heap() every time you are calling O(n.ln(n)) each time that things are added. While it is supposed to be O(ln(n))
|
|
| Aug 4, 2017 at 18:25 | answer | added | Loki Astari | timeline score: 2 | |
| Aug 4, 2017 at 18:15 | comment | added | Loki Astari |
Think abut how much easier it would have been to spot that you are missing the already visited list if you had simplified the code and used a priority_queue rather than doing it manually.
|
|
| Aug 4, 2017 at 18:13 | comment | added | Loki Astari | I know that. Its not about improving performance (which is the least important thing) it is about improving readability and maintainability (which is the most important thing). The amount of time developers will spend reading your code (multiple hours with many more because of the added complexity) will far exceed any performance increases you have at runtime (microseconds that may add up to a fraction of a second over a year, if it is running constantly). | |
| Aug 4, 2017 at 18:06 | comment | added | HenrikS | Actually, std::priority_queue just uses std::make_heap internally. So it won't improve performance. | |
| Aug 4, 2017 at 17:30 | comment | added | Loki Astari | This may be useful: en.cppreference.com/w/cpp/container/priority_queue | |
| Aug 4, 2017 at 17:29 | comment | added | Loki Astari | Dijkstra has an already visited list (in addition to the frontier list). SO not an exact implementation of dijkstra though very dijkstra like. | |
| Aug 4, 2017 at 15:58 | review | First posts | |||
| Aug 4, 2017 at 16:01 | |||||
| Aug 4, 2017 at 15:53 | history | asked | HenrikS | CC BY-SA 3.0 |