Tatsugiri's blog

How to calculate shortest path from start to end visiting a certain node
By Tatsugiri, history, 13 days ago, In English

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?

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

DFS? Find all the paths passing through $$$p_k$$$ and ending at $$$p_n$$$ and get the minimum cost/weight of all paths.

→ Reply
  • »
    »
    13 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    It is obvious that the number of paths is exponential

    → Reply
    • »
      »
      »
      13 days ago, # ^ |
      ← Rev. 2   Vote: I like it -10 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, path count is exponential. Just think of this construction:

        1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
.
.
.
        → Reply
»
13 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://stackoverflow.com/questions/16740739/shortest-path-between-three-points

not sure is it best, ILP isn't in poly time.

→ Reply
»
13 days ago, # |
  Vote: I like it +14 Vote: I do not like it

just two dijkstras: d(1,k)+d(k,n) ?

→ Reply
  • »
    »
    13 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    it may visit some nodes more than once

    → Reply
    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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...

      → Reply
      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        Yeah, I believe it works for nonnegative edge weights.

        → Reply
      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Yeah but maybe in the poster's problem he MUST not visit any node more than once

        → Reply
  • »
    »
    13 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    (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.

    → Reply
    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      I thought pk was given in forms of queries, if it is constant like N or M, of course one Dijkstra is enough

      → Reply
»
13 days ago, # |
  Vote: I like it +31 Vote: I do not like it

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)

→ Reply
  • »
    »
    12 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 days ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      → Reply