Shortest Path with max distance
- Lingua principale
- C++
- Stelle
- 392
- Fork
- 239
- Merge medio
- 1g 11m
- PR unite (30g)
- 20
Descrizione
I am interested in finding the one-to-many shortest path only if it is below a certain max distance D. If a node is farther than D, the distance shall be inf, as usual from a non reachable node. I am considering non negative weights (maybe also just positive).
My focus is mostly performance: I could run the full one-to-many search with Dijkstra and then simply post process the solution. But I expect that the node actually reachable within D are significantly less than the full graph.
Despite being possible to use the RCSP, this seems to me a simple extension of Dijkstra that I wonder it could be achieved in BGL.
My idea is would be to prevent a new node to be inserted in the queue if its distance from the source exceed D. From a quick glance at the BFS visit it does not seems possible to hack on that.
Any suggestion?
Guida per i contributori
Apri la guida per i contributori
Valutazione
Questa issue non è ancora stata valutata.