The Shortest Path Problem - Bidirectional Dijkstra's / Alt / Reach

This video is an overview of some shortest path algorithms and how they work. In particular we discuss Dijkstras algorithm, ALT, Bidirectional Dijkstras, and touch on concepts such as reach and highway hierarchies.

Jump to:
Dijkstras - 1:57
Bidirectional Dijkstras - 15:43
ALT - 8:50
Reach - 19:27
Highway Hierarchies - 23:53

[Dr.SamirKumarSadhukhan-jwwk]

Explain the state-of-the-art bidirectional heuristic search BAE* (Bidirectional A* with Error). You can take the heuristic as zero to get the particular case.

[christychan]

Thank you guys, very clear explanation! Really helps a lot!!

[amitaiperlstein]

What a great summary.
I believe there might be an error in the ALT algorithm:
The heuristic h(x), which estimates the distance from x to T (destination) does NOT obey the assumption h(x) <= d(x, y) + h(y).
Hence, I think it might be a mistake to stop searching once the node T is popped out of the stack.
Without the assumption h(x) <= d(x, y) + h(y) (which clearly would hold, should the heuristic be Euclidean dist), it isn't assured that there isn't a shorter path to T, via A for instance, which is still in the stack. We found a distance 16 from S to T. The distance via A is SUPPOSEDLY at least 17, but this estimate was reached partly with accurate calculation (from S to A), but also partially with a heuristic from A to T which does NOT obey the trivial lower bound assumption.

[Soedmaelk]

When you went over the ALT algorithm at around 10:00, isn't the distance from E to A = 15? E -> C -> S -> A?

[tigerinus]

10:04 Why do you have 11 instead of 8 for the distance from S to E?

[folyrd]

I'm working on presenting how reach is used in figuring out the shortest paths. However I feel there are a limited number of resources to understand the concept. This video and the actual paper by Ron Gutman, were the best I could find. And the reach concept is still not clear to me. Would you know of other helpful resources to understand reach easily?

[novicesim]

How do you/Is there any tutorial relating to simulating the Dijkstras algo on the google maps at 28:00?

[TunjungUtomo]

I'm building dynamic routing engine with the edge representing the latest road traffic situation, is there any way to quicken Dijkstra's contraction hierarchy?any input would be greatly appreciated :-)

[jatinmalik]

the bidirectional search you explained is not actually right!! the node you find at the termination condition may not be on the shortest path .so you have to check for side neighbours also !!! btw nice summary:)