CODEWITHSUNDEEP
algorithmgraphpathcomputer-scienceshortest
Loz
Loz

Reputation: 1

bi-directional really gives shortest path?

I was told by the cracking interview book that bi-directional algorithm give shortest path between 2 points in graph.

I don't get why it is guaranteed shortest path. Doesn't collision point change depended on vertexs' queuing order during breadth-first search?

thx

Upvotes: 0

Views: 55

Answers (1)

Cihan
Cihan

Reputation: 2307

Doesn't collision point change depended on vertexs' queuing order during breadth-first search?

Yes, it does. However, whichever node ends up being chosen, it will connect one of the shortest paths between the source and target nodes.

So if there are multiple such choices, it can be through any of them depending on queueing order as you said. But you are guaranteed that the resulting path will be of the same optimal length.

Upvotes: 1

Related Questions