Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 784
Pradhan Avatar asked Sep 06 '11 02:09

Pradhan


People also ask

How do you find the shortest path from one vertex to another?

The idea is to use Dijkstra's algorithm. In order to find the shortest distance from all vertex to a given destination vertex we reverse all the edges of the directed graph and use the destination vertex as the source vertex in dijkstra's algorithm.

How do you find the simple path between two vertices?

Approach: Either Breadth First Search (BFS) or Depth First Search (DFS) can be used to find path between two vertices. Take the first vertex as a source in BFS (or DFS), follow the standard BFS (or DFS). If the second vertex is found in our traversal, then return true else return false.

How do I find the shortest path in DFS?

And so, the only possible way for BFS (or DFS) to find the shortest path in a weighted graph is to search the entire graph and keep recording the minimum distance from source to the destination vertex.


2 Answers

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

like image 162
Beta Avatar answered Oct 12 '22 21:10

Beta


  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.

like image 31
Mu Qiao Avatar answered Oct 12 '22 20:10

Mu Qiao