FixTheRobot Explore Robotics / Navigation / M3 / M3-L1

This lab works on phones, but writing code is much easier on a laptop.

Navigation · Global Planning: Graph Search · M3-L1 · Beginner

Implement Dijkstra

Incident report · Meridian General Hospital

10:15. The pharmacy has a prescription for Ward B and Scout takes the short way, straight through the crowded waiting area. The orderlies shuffle aside, the delivery arrives eight minutes late, and the route log shows a path that was shortest in steps and expensive in everything else.

You will write Dijkstra's algorithm in three steps: the cost of the cheapest route, the route itself, and the nearest of three pharmacy windows from a single search.

Your task

    Simulation
    solution.pyLoading Python…
    Ctrl+Enter runs
    What Python can I use?

    Plain Python with math and heapq. Your code runs in a background worker: an endless loop is stopped after a few seconds and the page stays usable. It runs in your browser and is never sent anywhere.

    Hints

    What this lab teaches

    Stage 1 is the heart of the algorithm: a priority queue of tentative costs, a table of the best cost found so far for each cell, and the rule that a cell is final when it is popped, not when it is first seen. The starter marks cells as finished on discovery, which is correct for breadth-first search and wrong as soon as costs differ. Stage 2 turns the cost into a route by keeping a parent for every cell, and shows why breadth-first search, which minimises steps, is not the same as Dijkstra, which minimises cost. Stage 3 uses one search to answer a question about several goals, and asks what negative costs would do.

    Grading is result-based: your functions run on the practice ward and on freshly generated hidden wards, and are compared with exact costs, valid routes and the true cheapest goal. Routes of equal cost are all accepted.

    Theory for this lab

    Global Planning: Graph Search labs

    1. M3-L1: Implement Dijkstra: this lab.
    2. M3-L2: Implement A* with Search Replay
    3. M3-L3: Fix a Corner-Cutting Planner
    4. M3-L4: Replan When the Corridor Closes

    Educational simplification: a 4-connected grid, no diagonal moves, no robot footprint, and a move costs the sum of the values of the two cells it joins so that every answer is a whole number. Real planners add diagonal moves, a costmap and a controller (lessons M3-T1 and M3-T7).

    Get the next lab

    Get notified when new robotics labs are released. One email per new lab, nothing else.