search

pszufe / OpenStreetMapX.jl

OpenStreetMap (*.osm) support for Julia 1.0 and up
MIT License
118 stars 24 forks source link

Don't store dist as key in frontier #54

Closed blegat closed 2 years ago

blegat commented 2 years ago

In A*/Dijkstra, there is two approaches for the datastructure: 1) Use a heap, it's very cheap but you can't update the value of a node so you will store the node several times with different distances and once the first one comes out of the heap, you know you can just ignore the rest. Each operation is super cheap as it's just implemented as a Vector 2) Use a full-fledged priority queue where you can update values so you never store more elements as the number of nodes you have, but each operation is more costly.

Here, a full-fledged priority queue is used but the distance is stored as well so the same nodes will occupy several slots in the priority queue! In fact, we never check when a node is taken out of the priority queue that the color of this not is not already 2 so we may treat the same node several time!

This PR fixes the issue by not storing the distance in the key, it's in dists anyway.

pszufe commented 2 years ago

so now we have here a conflict with an earlier PR - needs to be resolved.

pszufe commented 2 years ago

Looks fine to me. Again we have conflict. Perhaps the changes are quite atomic :-)

blegat commented 2 years ago

Yes, I don't mind rebasing, it's worth it to have small self-contained changes :)