§ 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 $A$ to point $B$. We should find the path that fire travels. How do we do this? Well, we simply simulate a fire going through all paths from our initial point, and then pick the shortest path (ala Fermat). We interpret the graph edges as distances between the different locations in space.

• So we write a function $simulate :: V \times T \rightarrow 2^{V \times T}$, which when given a starting vertex $v : V$ and a time $t : T$, returns the set of 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 fire from $x$ reaches $p$, and we know the trajectory of the fire from $p$. The next time where a fire from $y$ reaches $p$, we don't need to recalculate the 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 the usual implementation: Order the events by time using a queue, and then add new explorations as we get to them.