1

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.

ChrisB
  • 2,497
  • 2
  • 24
  • 43
user3390917
  • 31
  • 1
  • 3
  • If you had a strict ordering on the intermediate nodes, then you are correct, just find the shortest path between each, in order. If you don't care about the ordering then k-shortest paths would eventually give you the answer, but it would be inefficient. A greedy algorithm might be the best option in this case, if it is ok to get a path that might not be the absolute shortest. – Destruktor Jan 13 '17 at 17:31
  • 1
    looks similar to this: [http://cs.stackexchange.com/questions/14977/shortest-path-that-passes-through-specific-nodes](http://cs.stackexchange.com/questions/14977/shortest-path-that-passes-through-specific-nodes) – Destruktor Jan 13 '17 at 17:41
  • The other question asks for acyclic graphs. Also the answer is just for shortest walk not a path. – Saeed Amiri Jan 14 '17 at 01:23
  • Possible duplicate of [Find the shortest path in a graph which visits certain nodes](http://stackoverflow.com/questions/222413/find-the-shortest-path-in-a-graph-which-visits-certain-nodes) – Dolev Feb 17 '17 at 15:46

1 Answers1

0

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.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83