Build a diff: the greedy walk

Traces the cheapest route across a small map of towns, one road at a time. This lesson draws the diff table from the last build as a map too, and finds the cheapest route across it while visiting almost none of it.

Before you start. Build a diff: the table built a diff from a table with one cell for every pair of lines: correct, but 16,000-line files already needed 2.2 GB, because the table fills every cell even when one line changed. Shortest Paths, Worked (Dijkstra, Bellman-Ford, A*) found the cheapest route across a map by always finishing the nearest unfinished town first, and Git's diff (Myers' algorithm) - the case study, later in this track, shows how git answers it; here you build that answer yourself and time it against the table.