CODEWITHSUNDEEP
algorithm
NSF
NSF

Reputation: 2549

Shortest path through certain vertex in directed graph

Say we have a strongly connected directed graph G (V,E) with positive edge weights and V0 belongs to V. Write an algorithm to find the shortest paths between all pairs of nodes through V0

An interview question. Clearly we could use Bellman-Ford which takes O(VE).

However there must exist a better solution. Any help please?

Upvotes: 1

Views: 3609

Answers (1)

Qnan
Qnan

Reputation: 3744

I think you could even use Dijkstra's algorithm. Run it once to find the shortest paths from V0 to all other vertices and then once more to find the shortest path from every other vertex to V0 (this is the same as running regular Dijkstra on the graph with reversed edges). Then for any pair (V1,V2) concatenate paths from V1 to V0 and from V0 to V2.

Upvotes: 3

Related Questions