1

I have a problem, where I have a non-directed, non weighted graph, with a starting node s, a sink node t, and a special node w.

enter image description here

Now, I need to find a simple path from s to t, that goes from s to t, with the one constraint that the path should go through w. Just reapeating no vertices

I've seen variations of this question here, where people are using a weighted graph, and are trying to find the shortest path. This makes the problem into a variation of travelling salesman, which would make it np-hard.

but i my case, can I solve this simple problem in polynomial time? since I have to few constraints?

n00bster
  • 379
  • 4
  • 12
  • 1
    This merely reduces to finding path from s to w and then finding a path from w to t. Nothing there makes the problem easier. – wcochran Oct 27 '20 at 16:02
  • so as long as im dealing with a simple path, where vertices are not reapeated, this problem can not be polynomial? and I should just reduce it to travelling salesman? – n00bster Oct 27 '20 at 16:15
  • Finding the shortest path is not NP-complete (see Dijkstra). TSP would require you to visit every node exactly once -- that is what makes it difficult. Forcing some intermediate node does not makes either of these simpler. – wcochran Oct 27 '20 at 16:25
  • It sounds like you are suggesting that I should just run dijkstra twice, first finding the path from s-w and then from w-t. But how would I then avoid using the same vertex twice? – n00bster Oct 27 '20 at 16:34
  • Not quite that simple since you can't repeat nodes. Actually adding an intermediate node makes the problem harder (its a small step towards TSP). See answers to https://stackoverflow.com/questions/222413/find-the-shortest-path-in-a-graph-which-visits-certain-nodes – wcochran Oct 27 '20 at 16:49
  • Here, it looks like dijkstra is run, and then all paths that involve node w are examined – n00bster Oct 27 '20 at 17:00
  • You can actually just run dijkstra once from node w outwards(without a target node). This gives you the shortest path from w to all other nodes in E log(E), including the starting and ending node. From here, simply return distToS + distToE – timg Oct 28 '20 at 04:15
  • 1
    But could'nt I end up walking on the same vertex twice? – n00bster Oct 28 '20 at 10:39

0 Answers0