§ 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 AA to point BB. 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 simulate::V×T2V×Tsimulate :: V \times T \rightarrow 2^{V \times T}, whichwhen given a starting vertex v:Vv : V and a time t:Tt : T, 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 xx reaches pp, and we know the trajectory of the fire from pp. Thenext time where a fire from yy reaches pp, 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.