boostorg / boostorg/graph

Shortest Path with max distance

Aperta
#444 3 commenti 0 reazioni 0 assegnatari Vedi su GitHub
algorithm
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.

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.