CODEWITHSUNDEEP
c++boostshortest-pathdijkstra
HuyNA
HuyNA

Reputation: 628

Find shortest path using Boost Dijkstra with specified MAX DISTANCE

I love using boost's dijkstra implementation to find the shortest path from a node

However, in my current problem, I have a huge graph and only need to find shortest paths to nodes that are within a certain distance

I can implement this myself, but I believe boost's implementation is much more efficient than mine, so I prefer to use boost for the task

I just wonder if there is a way to tell boost's dijkstra to stop looking for shortest paths if nodes are too far -- as it will significantly speed up the algorithm in this case

Upvotes: 2

Views: 1064

Answers (1)

Pavel Gatnar
Pavel Gatnar

Reputation: 4053

It is a very simple modification of the Dijkstra algorithm. While you iterate over outgoing edges from vertex v, just ignore each edge e, where e.weight + v.dist > max.

Upvotes: 2

Related Questions