CODEWITHSUNDEEP
algorithmgraphgraph-theory
Craig
Craig

Reputation: 1940

Is there a graph algorithm to find shortest path between nodes, incorporating nodes to avoid?

Let's say I have a graph with nodes that represent locations. Starting at some node N, I want to reach another node M via the shortest path possible. The catch is that there some nodes I want to avoid, staying some distance from them (say at least D nodes away).

Is there a graph algorithm that can solve the shortest path problem with the node avoidance requirement? Would a weighted graph (with infinite length edges emanating from the to-be-avoided nodes) be a solution here?

Upvotes: 0

Views: 317

Answers (1)

Richard
Richard

Reputation: 61249

Temporarily eliminate the nodes you must avoid and those near them or change the weights of the appropriate edges to infinity. Then use any standard path-finding algorithm.

Upvotes: 3

Related Questions