CODEWITHSUNDEEP
pythonshortest-pathdijkstra
Linton Charles
Linton Charles

Reputation: 113

Shortest path passing through at least 1 node from a subset of nodes

I want to implement a python function that generates the shortest path from a source node to a destination node in a directed, weighted graph. It has to include at least one node from a subset of nodes in the graph and the path has to be the shortest possible in the subset. How can you achieve this in O(ElogV) time where E and V are the number of edges and nodes?

Upvotes: 1

Views: 375

Answers (1)

BrokenBenchmark
BrokenBenchmark

Reputation: 19223

Run Djikstra's from the source node. Then, reverse all the edges in the graph. On this new graph, run Djikstra's from the destination node. The node which has the minimum sum of the distance from the source node (in the original graph) and the distance from the destination node (in the reversed graph) is the node that the shortest path goes through. Once this node has been identified, you can read off the actual nodes in the shortest path.

Djikstra's takes O(E log V) time, and we run it twice. Finding the node with the minimum sum takes O(V) time, and reading off the answer takes O(E) time. So, the runtime of this algorithm is O(E log V).

This answer is deliberately incomplete, per these recommendations. If you're still stuck after several days, post a comment and I can advise further.

Upvotes: 2

Related Questions