§ Motivating Djikstra's
Usually I've seen Djikstra's algorithm presented as a greedy algorithm,
and then an analogy given to "fire" for the greediness. We can reverse
this presentation start with the "fire", and the discretize the "fire" solution
to arrive at Djikstra's
§ The fire analogy
- Assume we want to find the shortest path from point to point . Weshould find the path that fire travels. How do we do this? Well, we simplysimulate a fire going through all paths from our initial point,and then pick the shortest path (ala Fermat). We interpret the graphedges as distances between the different locations in space.
- So we write a function , whichwhen given a starting vertex and a time , returns the setof vertices reachable in at most that time, and the time it took to reach them.
- Notice that we are likely repeating a bunch of work. Say the firefrom reaches , and we know the trajectory of the fire from . Thenext time where a fire from reaches , we don't need to recalculatethe trajectory. We can simply cache this.
- Notice that this time parameter being a real number is pointless;really the only thing that matters are the events (as in computational geometry),where the time crosses some threshold.
- By combining the two pieces of information, we are led to theusual implementation: Order the events by time using a queue, and thenadd new explorations as we get to them.