Find shortest path from Vertex u to v passing thro

问题:

In a directed graph with non-negative edge weights I can easily find shortest path from u to v using dijkstra's. But is there any simple tweak to Dijkstra's so that I can find shortest path from u to v through a given vertex w. Or any other algorithm suggestions?

回答1:

Find the shortest path from u to w, then the shortest path from w to v.

回答2:

1. Find shortest path from u to w
2. Find shortest path from w to v

Then u->w->v is the shortest path.

You can do it by running Dijkstra for two times, but you can also apply the Floyd-Warshall algorithm.

回答3:

This problem is NP-hard, so finding a polynomial time solution is unlikely. See this cstheory post for more details.

回答4:

Using the following approach we could run the algorithm just once:

set v_visisted = false
    Start from w and find shortest path to u
    if v was visited during shortest path search to u, set v_visted = true
    If v is part of shortest path from w->u then
          exit with result ( # the path would be u->v->w->v ) 
       else
           if v_visited= true then we already know values for w->v. We have a solution.
           else save path from w->v and switch u to source and find shortest path to v.

Note that running the shortest path from u to v is effectively continuing the algo's first run. Therefore, we are running the algo just once, by tracking if we visited 'v'.

回答5:

Looks like finding u to w and then finding w to v, concatenating both results. Would it work?