Find shortest path from Vertex u to v passing through a vertex w?

7
votes

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?

5
algorithmgraphdijkstrashortest-path
Is it possible to find that a path exists from u to v that has w in it, not necessarily the shortest path. Can it be done in poly(n) time, where n is the number of vertices in the graph. - Rahul Kadukar
For an arbitrary graph, this problem is NP-hard. See cstheory.stackexchange.com/questions/25077/… for more details. - Zach Langley

5 Answers

9
votes

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

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

4
votes

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

1
votes

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

0
votes

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