§ 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.