Algorithm for shortest path between 2 vertices

1
votes

I have a weighted Graph with all positive weights.I need to find the shortest path from vertex x to vertex y. Should I prefer in this case the Floyd–Warshall algorithm over Dijkstra's algorithm since I'm not interested in shortest path from a single source to all vertices but just between specific 2. I can restrict Floyd–Warshall to care only about the 2 vertices of interest, x and y. In that case it looks to me that Floyd–Warshall can find he shortest path from vertex x to vertex y in O(|V|).

Is that correct ?

Thanks!

1
algorithmfloyd-warshall
How would you restrict Floyd-Warshall to two vertices? - Nico Schertler
en.wikipedia.org/wiki/Floyd–Warshall_algorithm - I'll just do a single for loop on k where i,j will be constant - Tomer
That will only give you the shortest path with up to one intermediate vertex only. - Nico Schertler
Yes my bad you are correct! - Tomer
Then is your question answered with this insight? - Nico Schertler

1 Answers

1
votes

I would recommend a breadth-first search starting at both ends in parallel. With a hash of nodes visited so that you know when the searches met.

Assuming a random graph with decent connectivity, your average run-time will be on the order of sqrt(V).

This is a common trick to use to find, for example, the distance between two people in a social graph without having to look at most of it.