Given an undirected graph with positive cost number on each edge, I need to calculate shortest path from p1 to pn node visiting a certain node pk(pk is not a start or end node).
The main problem is in restriction that the solution path should not visit any node more than once. Because of that, there may be no solution at all.
Is there any polynomial-time algorithm to solve the problem, or can it be proven np-hard?
DFS? Find all the paths passing through $$$p_k$$$ and ending at $$$p_n$$$ and get the minimum cost/weight of all paths.
It is obvious that the number of paths is exponential
I think not. It's O(V+E). In the worst case(and only in this problem), DFS will pass through all edges and nodes.
Is something wrong with this?
Yeah, path count is exponential. Just think of this construction:
Oh, ok, sorry
just two dijkstras: d(1,k)+d(k,n) ?
it may visit some nodes more than once
That sometimes must happen... For example, If your graph is a tree and the node is one of the nodes in the shortest_path(k,n) , then you have to visit -> shortest_path(1,k)+shortest_path(k,1)+shortest_path(1,n)
I just want to say that it won't visit any nodes more than once if it doesn't need to...
Yeah, I believe it works for nonnegative edge weights.
Yeah but maybe in the poster's problem he MUST not visit any node more than once
Then he MUST say that it's impossible :)))
(I do know that this is not a correct solution, just wanted to comment this)
Two Dijkstras is overkill. Only one Dijkstra from $$$p_k$$$ is enough. However, this still does have the issue of visiting some node twice.
I thought pk was given in forms of queries, if it is constant like N or M, of course one Dijkstra is enough
Seems like it can be solved with mincostflow approach, there are two units which go from source to start and end vertices and two units can be transfered from vertex pk to target, you need to find min cost max flow while the cost of transfering one unit between vertices is 1, except source and target vertices. (Sorry for bad english)
May be I didn't understand something, but how you ensure that the flow will be like path p1->pk->pn, but not two separated paths: p1 to pn and pk_out to pk_in
The flow goes from source to target by 2 paths: 1) Through start vertex and pk 2) Through end vertex and pk. The resulting path between start and end is combination of these two paths with source and target vertices excluded
Got it, in undirected graph it should work. Thank you!