Menu
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?
784
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.
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.
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.
Find the shortest path from u to w, then the shortest path from w to v.
162
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.
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
