CODEWITHSUNDEEP
algorithmgraphgraph-algorithmdijkstrashortest-path
user3390917
user3390917

Reputation: 31

Directed weighted graph shortest path with obligatory nodes to pass

Hello i'm trying to find the best algorithm to solve this problem.

I have a a graph that i must find the shortest path between Start and End node specified but that must pass on specific user input nodes.

There is no order for the must pass nodes and you can visit more than once each node.

If i consider each must pass node need to be reached on a specific order calculating the shortest path to each stop first would be easier right?

Is K Shortest path the way to go to solve this problem? Calculate the shortest Path and go from there, till we find the shortest that pass on all must pass nodes?

Here is an example graph i draw enter image description here

Nodes 4 and 6 are must pass, and i need to find shortest path between 1 and 5.

Upvotes: 1

Views: 889

Answers (1)

Saeed Amiri
Saeed Amiri

Reputation: 22555

It is well known that 2 disjoint paths problem is NP-complete in digraphs. Their proof has a graph G and two source vertices s1,s2 and two terminals t1,t2. The task is to find two internally vertex disjoint paths p1,p2 s.t p1 connects s1 to t1 and p2 connects s2,t2. We can model your problem simply with disjoint paths. In the graph provided in the above mentioned hardness proof, just identify s2,t1 and make it a new vertex s2t1. Then there are two disjoint paths in the original graph if and only if there is a path starting at s1 goes through s2t1 and ends at t2. This means even finding such a path in directed graphs is hard. Not even optimization version.

But if the graph has special structure it can get easier. Like e.g. on acyclic graphs it is easier.

Upvotes: 0

Related Questions