How to find the shortest path from vertex u to v while at least visiting one target for directed graph?

user_1570777 0
Viewed 286

I am struggling to perform this in O(|E|log(|V|)) worst-case time complexity where E is the list of edges and V is the vertices in the graph.

So far I tried to use an adjacency list. I first sort the graph from starting vertex u using Kahn's topology algorithm.

I then look for the next target in the sorted topology and push the minimum distance of going from vertex u to v while traversing through the target into a min-heap. I did this by using Dijkstra's algorithm to find the minimum distance from u to the target requiring minimum overall distance. I also find the minimum distance from the target to vertex v.

Edit: Solution for directed graph

I found a solution by creating a copied graph with all the edges in reversee. I run dikjistra from source to destination then from run dikjstra again from destination to source with the graph with all reversed edges. I find overall distancing involving traversing at least one target along the way then I reuse the distance I got from the previous dikjistra executions to find the shortest path.

shortest-path graph-theory algorithm
1 Answers

let DistSrc[i] denote the shotest distance of node i from source(here u) and DistDes[i] denote the shotest distance of node i from destination.

Both DistSrc and DistDes can be found by dijkstra algorithm.

iterate over all target nodes (say ti) and and take the minimum of (DistSrc[ti]+DistDes[ti]) over all ti.

user_125907980
Related