A First Taste of Algorithms · Lab 5: Dots and Lines

5. Price tags on the town

The chapter’s town, with weights — a dictionary of neighbor lists where each neighbor comes with a price, as a (place, minutes) tuple:

town = {
    "Home":    [("Park", 2), ("School", 9), ],
    "Park":    [("Home", 2), ("School", 5), ("Library", 9), ("Gym", 11)],
    "School":  [("Park", 5), ("Home", 9), ("Library", 1), ("Cafe", 7)],
    "Library": [("School", 1), ("Park", 9), ("Cafe", 4)],
    "Cafe":    [("Library", 4), ("School", 7), ("Gym", 3)],
    "Gym":     [("Park", 11), ("Cafe", 3)],
}

Dijkstra’s protocol, exactly as you played it with coins — tags, settle the cheapest, relax its edges:

def dijkstra(graph, start):
    tags = {start: 0}                   # tentative prices; absent = infinity
    settled = set()
    while len(settled) < len(graph):
        cheapest = None                 # scan for the cheapest unsettled tag
        for place in tags:
            if place not in settled:
                if cheapest is None or tags[place] < tags[cheapest]:
                    cheapest = place
        if cheapest is None:
            break                       # the rest is unreachable
        settled.add(cheapest)
        for edge in graph[cheapest]:
            place = edge[0]
            cost = tags[cheapest] + edge[1]
            if place not in tags or cost < tags[place]:
                tags[place] = cost      # relax: the detour wins
    return tags

print(dijkstra(town, "Home"))

(None is Python’s word for “nothing yet” — the scan starts with no champion and crowns the first candidate.) Check every tag against the chapter’s hand-run: Park 2, School 7, Library 8, Café 12, Gym 13 — five answers, five detours. Then rebuild town as your actual neighborhood, six or seven places with honest walking-minutes, and find something true you didn’t know about your own streets.

Break it

Predict first. Run second. Explain any gap third.

1. The desynchronized graph from §1: delete "gym" from lobby’s neighbor list (keep lobby in gym’s). Predict bfs(hallways, "gym") and then bfs(hallways, "lab") — same reachability or different? You have built a one-way door. Real graphs (the web, who-follows-whom) are full of them; what single sentence of the §1 convention did you break, and which of the two BFS runs is the one that can no longer find everything?

2. In maze_bfs, remove the border: change your maze’s top row to open floor and run from S. Predict the failure before running — wrong answer, error, or infinite loop? — then read the error’s last line and explain which innocent-looking expression walked off the world. (Two repairs exist: rebuild the wall, or teach the neighbor-check to refuse positions outside the maze. Implement the second; the first you already had.)

3. The road that pays you. First, make Dijkstra’s promises audible: add one line right after settled.add(cheapest) — print("settled:", cheapest, "at", tags[cheapest]) — and rerun the honest town. Compare the announcements with the final notebook: they agree perfectly, every time, on every honest map (that agreement is the deep-water theorem talking). Now build the chapter’s Problem 3.3 graph using Break-it 1’s one-way doors — {"Home": [("B", 2), ("C", 3)], "B": [], "C": [("B", -2)]} — predict the announcements, and run it. Catch the exact moment the algorithm publicly settles a lie (which vertex, announced at what price, versus the truth you can see by eye?). Then two follow-ups: (a) point to the clause of the deep-water proof that this graph kills, quoting it; (b) the final notebook actually shows the right number anyway — find the line of our code that quietly forgave the lie after the announcement, and explain why you still must not trust this on bigger graphs (what if the lying vertex’s wrong tag had been used to relax its neighbors before the correction arrived?). One warning while experimenting: keep negative edges one-way here. A negative two-way road lets a walker pace back and forth earning money forever, and “cheapest route” stops meaning anything — the question itself, not just the algorithm, dies. (Restore the town when done; it has suffered enough.)

4. The knight’s ripple (finishing Problem 2.5). A chessboard is rows and columns 0–7; a knight at (r, c) can jump to eight positions: (r±1, c±2) and (r±2, c±1), board permitting. Adapt maze_bfs — same skeleton, different neighbor list, and the “board permitting” check is Break-it 2’s repair earning rent. Compute the fewest moves from (0, 0) to (7, 7), compare with the prediction you wrote in the problem set, and then print the full dist notebook and find the squares that are hardest for a corner knight to reach. Are they where you’d have guessed?

All 32 chapters of A First Taste of Algorithms · Foundations · All courses