Build a City Emergency Response Router

Introduction

30 Second Summary

When an ambulance races through city streets, the difference between choosing a short route through gridlocked traffic versus a longer highway could mean 20 minutes lost. That's a life-or-death algorithm choice.

In this project, you will build an emergency response routing system that models a city as a weighted graph, implements two pathfinding algorithms from scratch, and visually proves why the "obvious" shortest path is sometimes the worst choice.

What You'll Build

You'll run your router and watch it find two completely different paths for the same ambulance call, then see both routes drawn on a city map with travel times proving one algorithm saves 20 minutes over the other.

By the end of this project, you'll have:

• A city road network modeled as a weighted graph with 10 intersections and 14 road segments, visualized with Matplotlib so you can see every intersection and travel time on screen.
• Your own BFS implementation that finds routes by minimizing hops, revealing its dangerous blind spot when edges carry different weights.
• Your own Dijkstra's algorithm using a priority queue that finds the genuinely fastest route, validated against NetworkX's built-in to confirm correctness.
• Secret Mission: Implement A* search with a heuristic function to find paths even faster than Dijkstra.

Are there any prerequisites?

You should be comfortable with basic Python (functions, loops, dictionaries, and classes) and familiar with data structures like lists, sets, and queues. No prior graph theory knowledge is needed.

Before We Start

Before We Start...

Before we dive in, let's lock in what you're about to build and why it matters.

Set Up Your Project

To build an emergency response router, you need two key libraries: one for representing the city as a graph, and one for visualizing the routes your algorithms find.

In this step, you'll create a project folder, set up a virtual environment, and install NetworkX and Matplotlib. By the end, your project file will be ready with all the imports you need to start modeling the city.

In this step, get ready to:

• Create a project folder with a virtual environment.
• Install NetworkX and Matplotlib.
• Create the project file and verify everything runs.

Create a project folder and virtual environment

A virtual environment keeps this project's libraries isolated from your system Python. This prevents version conflicts with other projects on your machine.

• Move to your Desktop by running this command:

cd ~/Desktop

• Create your project folder and move into it by running these commands:

mkdir emergency-router
cd emergency-router

• Confirm the folder exists by running:

ls ~/Desktop

You should see emergency-router listed in the output.

• Create a virtual environment by running:

python -m venv venv

• Activate the virtual environment:

macOS

• Activate by running:

source venv/bin/activate

This same command works on Linux.

Windows

• Activate by running:

venv\Scripts\activate

Your terminal prompt now shows (venv) at the start. This confirms the virtual environment is active.

Don't see (venv) in your prompt?

Make sure you ran the activation command from inside the emergency-router folder. The venv folder must exist in your current directory.

On Windows PowerShell, you may need to allow script execution first. Run Set-ExecutionPolicy -Scope CurrentUser -ExecutionPolicy RemoteSigned and try again.

help me activate my Python virtual environment

Install dependencies

NetworkX provides graph data structures and algorithms. Matplotlib handles all the visualization so you can see your city network and routes on screen.

• Install both libraries by running:

pip install networkx==3.6.1 matplotlib==3.11.0

What does this command do?

• networkx==3.6.1 installs the exact version of NetworkX you need for graph modeling and pathfinding validation.
• matplotlib==3.11.0 installs the exact version of Matplotlib for rendering graphs and route comparisons as images.
• Pinning versions ensures your project behaves the same way regardless of when you run it.

You should see output ending with Successfully installed followed by the package names and versions.

Seeing a permissions error or install failure?

Make sure your virtual environment is active. You should see (venv) in your prompt. If not, go back and run the activation command.

If you see a network timeout, check your internet connection and try the command again.

help me install networkx and matplotlib in my virtual environment

Create the project file and verify imports

• Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
• Type VS Code (or your preferred editor name) and press Enter to open it.
• Open the emergency-router folder from your Desktop.
• Create a new file called emergency_router.py.

• Add the following imports to emergency_router.py:

import networkx as nx
import matplotlib.pyplot as plt
from collections import deque
import heapq

What do these imports do?

• networkx as nx gives you graph data structures and built-in algorithms for validation later.
• matplotlib.pyplot as plt handles drawing the city graph and route comparison images.
• deque from collections is a double-ended queue you'll use for BFS.
• heapq is Python's built-in priority queue module, essential for Dijkstra's algorithm.

• Save emergency_router.py.

Before you run the verification command, what do you expect to see if all four libraries imported correctly?

• Verify your setup by running this command in your terminal:

python -c "import networkx; import matplotlib; print(networkx.__version__, matplotlib.__version__)"

You should see 3.6.1 3.11.0 printed with no errors.

Seeing a ModuleNotFoundError?

This means Python cannot find the libraries. Check that (venv) appears in your terminal prompt. If it does not, activate your virtual environment again and rerun the command.

If the versions printed don't match exactly, that's fine as long as the command runs without errors.

help me fix my Python import errors for networkx and matplotlib

✔️ Awesome, I've got everything!

Great. Double check you've saved emergency_router.py and you're ready to move on.

ⓧ I'd like to double check the full code

Here's what emergency_router.py should contain at this point:

import networkx as nx
import matplotlib.pyplot as plt
from collections import deque
import heapq

Your environment is ready. Next up, you'll model the city as a weighted graph and see it rendered on screen.

Model the City as a Graph

Your environment is ready with NetworkX and Matplotlib installed. Now comes the foundational skill of algorithm design: translating a real-world problem into a data structure that an algorithm can process.

An ambulance needs to get from a hospital to an emergency site through a city's road network. Each road has a different travel time based on distance and traffic. In this step, you will model those roads as a weighted graph and visualize it so you can trace paths by hand before writing any pathfinding algorithms.

In this step, get ready to:

• Build a weighted graph representing city intersections and roads.
• Visualize the graph with labeled nodes and edge weights.
• Confirm the graph structure by checking node and edge counts.

Build the weighted graph

A graph has two components: nodes (the intersections) and edges (the roads connecting them). Each edge carries a weight representing travel time in minutes.

• In emergency_router.py, add the following function below your import statements:

# --- Graph Construction ---

def build_city_graph():
    """Build a weighted graph representing a city road network."""
    G = nx.Graph()

    # Each tuple is (intersection_A, intersection_B, travel_time_minutes)
    roads = [
        ("Hospital", "Downtown_A", 15),
        ("Downtown_A", "Downtown_B", 12),
        ("Downtown_B", "Emergency_Site", 10),
        ("Hospital", "Highway_On", 3),
        ("Highway_On", "Highway_1", 4),
        ("Highway_1", "Highway_2", 3),
        ("Highway_2", "Highway_Off", 4),
        ("Highway_Off", "Emergency_Site", 3),
        ("Hospital", "Suburb_A", 8),
        ("Suburb_A", "Downtown_A", 6),
        ("Suburb_A", "Highway_On", 5),
        ("Downtown_B", "Highway_Off", 7),
        ("Suburb_A", "Suburb_B", 9),
        ("Suburb_B", "Emergency_Site", 11),
    ]

    G.add_weighted_edges_from(roads)
    return G

What does this code do?

This function builds a city with 10 intersections connected by 14 roads. The graph is deliberately designed with two distinct route types:

• A short-hop downtown path with heavy traffic (high weights: 15 + 12 + 10 = 37 minutes for 3 hops).
• A longer highway route with fast travel (low weights: 3 + 4 + 3 + 4 + 3 = 17 minutes for 5 hops).

This design will expose a critical difference between algorithms later: an algorithm that counts hops will pick the downtown route, while one that counts travel time will pick the highway.

• Save emergency_router.py.
• Verify the graph builds correctly by running this command:

python -c "from emergency_router import build_city_graph; G = build_city_graph(); print(G.number_of_nodes(), G.number_of_edges())"

You should see 10 14 printed in your terminal. That confirms 10 intersections and 14 roads loaded successfully.

Seeing an ImportError or ModuleNotFoundError?

• Make sure your terminal is inside the emergency-router folder where emergency_router.py lives.
• Confirm your virtual environment is still activated (you should see (venv) in your terminal prompt).
• Check that the filename is exactly emergency_router.py with an underscore, not a hyphen.

Why can't Python find my module?

Visualize the graph

A graph in code is invisible until you render it. Visualization lets you trace paths by hand and confirm the structure before writing algorithms.

• In emergency_router.py, add the visualization function and the main block below build_city_graph():

def visualize_graph(G, title="City Road Network"):
    """Visualize the city graph with edge weights."""
    # Use a fixed seed for reproducible node positioning
    pos = nx.spring_layout(G, seed=42)

    plt.figure(figsize=(12, 8))
    nx.draw_networkx_nodes(G, pos, node_size=700, node_color="lightblue")
    nx.draw_networkx_labels(G, pos, font_size=8, font_weight="bold")
    nx.draw_networkx_edges(G, pos, width=2, alpha=0.6)

    # Display travel times on each edge
    edge_labels = nx.get_edge_attributes(G, "weight")
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=7)

    plt.title(title)
    plt.axis("off")
    plt.tight_layout()
    plt.savefig("city_graph.png", dpi=150, bbox_inches="tight")
    plt.show()
    print(f"Graph saved to city_graph.png")
    print(f"Nodes: {G.number_of_nodes()}, Edges: {G.number_of_edges()}")

What does this code do?

• nx.spring_layout(G, seed=42) computes x,y positions for each node using a force-directed layout. The seed=42 makes the positions identical every time you run it.
• The nx.draw_networkx_* functions draw nodes as circles, labels as text, and edges as lines.
• nx.get_edge_attributes(G, "weight") pulls the travel time from each edge so you can display it on the graph.
• plt.savefig saves a PNG to disk as a backup in case the interactive window has issues on your system.

• Now add the main block at the very bottom of the file:

# --- Main ---

if __name__ == "__main__":
    city = build_city_graph()
    visualize_graph(city)

What is the __main__ block?

The if __name__ == "__main__" guard means this code only runs when you execute the file directly (python emergency_router.py). It won't run if another file imports a function from this module.

Run the script and confirm graph statistics

Before you run, think about what you expect to see. You defined 10 intersections and 14 roads with travel times. What should the visualization look like?

• Save emergency_router.py.
• Run the script:

python emergency_router.py

A Matplotlib window opens showing your city graph. You should see 10 light-blue circles (intersections) connected by lines, with numbers on each line showing travel time in minutes.

After you close the window, your terminal prints:

Graph saved to city_graph.png
Nodes: 10, Edges: 14

• Confirm that city_graph.png now exists in your project folder by running:

ls

You should see city_graph.png and emergency_router.py listed in the output.

What do the statistics confirm?

Nodes: 10 means all 10 intersections (Hospital, Downtown_A, Downtown_B, Emergency_Site, Highway_On, Highway_1, Highway_2, Highway_Off, Suburb_A, Suburb_B) loaded correctly.

Edges: 14 means all 14 road segments are connected with travel times. The graph is ready for pathfinding algorithms.

Not seeing the graph window?

• Some systems need the TkAgg backend for interactive display. Check that city_graph.png was saved to your folder. If the PNG exists, open it manually to view your graph.
• If you see an error about tkinter, the PNG file is your fallback. The image contains the same visualization.
• Confirm your virtual environment is activated and you installed matplotlib inside it.

Why isn't the matplotlib window appearing on my system?

✔️ Awesome, I've got everything!

Great. Double check you have saved emergency_router.py and can see city_graph.png in your project folder.

ⓧ I'd like to double check the full code

Your emergency_router.py should contain these sections in order. Scroll up and confirm each is present:

• The four import lines at the top (networkx, matplotlib.pyplot, deque, heapq).
• The build_city_graph() function defining 14 road tuples and calling G.add_weighted_edges_from(roads).
• The visualize_graph() function using nx.spring_layout, drawing nodes/edges/labels, and printing node and edge counts.
• The if __name__ == "__main__" block calling build_city_graph() then visualize_graph(city).

Your city is now a data structure an algorithm can process. Next up, you will write BFS to find a route through this graph and discover exactly why counting hops is not the same as finding the fastest path.

Find Routes with BFS

You have a city modeled as a graph. Now you need to find routes through it.

BFS (Breadth-First Search) is the simplest pathfinding algorithm. It explores the graph layer by layer, finding the path with the fewest hops. You'll implement it from scratch to internalize how graph traversal works. But there's a catch: BFS treats every edge as equal, so when edges have different costs, BFS can pick a terrible path.

In this step, get ready to:

• Implement BFS from scratch using a deque and visited set.
• Write a helper function to calculate total travel time for any path.
• Run BFS on the city graph and observe which route it picks.

Implement BFS from scratch

BFS works by exploring all neighbors at the current depth before moving deeper. It uses a queue (first-in, first-out) to track which nodes to visit next, and a visited set to avoid re-exploring the same node.

• In emergency_router.py, find the comment # --- Main --- near the bottom of the file.
• Add the following BFS function directly above that comment:

# --- BFS Pathfinding ---

def bfs_shortest_path(graph, start, goal):
    """Find path using BFS (minimizes hops, ignores weights)."""
    visited = set()
    queue = deque([(start, [start])])
    visited.add(start)

    while queue:
        current, path = queue.popleft()

        if current == goal:
            return path

        for neighbor in graph.neighbors(current):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None

What does this code do?

• queue = deque([(start, [start])]) starts the queue with the starting node and a path containing just that node. Each queue entry is a tuple of (current_node, path_so_far).
• queue.popleft() grabs the oldest entry (FIFO order), ensuring BFS explores layer by layer.
• The visited set prevents revisiting nodes, which would create infinite loops in a graph with cycles.
• When current == goal, BFS has found the shortest path by hop count. It returns immediately.

• Save emergency_router.py and run it to confirm no syntax errors:

python emergency_router.py

The graph visualization window opens as before. Close it and confirm no error messages appeared in the terminal.

Seeing a syntax error?

• Check that your function is placed above the # --- Main --- comment, not inside another function.
• Confirm the from collections import deque import is still at the top of the file (it was added in the previous step).

Help me debug my BFS function in emergency_router.py

Now add the helper function that calculates the total travel time along any path. BFS finds the path, but you need this function to reveal how long that path actually takes.

• Add this function directly below bfs_shortest_path, still above the # --- Main --- comment:

def calculate_path_time(graph, path):
    """Calculate total travel time for a path."""
    total_time = 0
    for i in range(len(path) - 1):
        total_time += graph[path[i]][path[i + 1]]["weight"]
    return total_time

What does this code do?

This walks through each consecutive pair of nodes in the path and looks up the edge weight between them. The sum of all edge weights gives the total travel time in minutes.

Run BFS and display the result

Your BFS and helper functions are ready. Now update the main block to call them and print the route BFS finds.

• In emergency_router.py, find the if __name__ == "__main__": block at the bottom.
• Replace the entire main block with this updated version:

# --- Main ---

if __name__ == "__main__":
    city = build_city_graph()
    visualize_graph(city)
    bfs_path = bfs_shortest_path(city, "Hospital", "Emergency_Site")
    bfs_time = calculate_path_time(city, bfs_path)
    print(f"BFS Path: {' -> '.join(bfs_path)}")
    print(f"Hops: {len(bfs_path) - 1}, Travel time: {bfs_time} minutes")

What does this code do?

• bfs_shortest_path(city, "Hospital", "Emergency_Site") runs your BFS to find a route from the hospital to the emergency.
• calculate_path_time(city, bfs_path) reveals the actual travel time of the route BFS chose.
• The print statements show the full path, hop count, and total minutes so you can evaluate BFS's decision.

Before you run this, think about which route BFS will pick. Remember: BFS minimizes hops (number of edges), not travel time. Looking at your graph, which path from Hospital to Emergency_Site has the fewest hops?

• Save emergency_router.py and run the script:

python emergency_router.py

Close the graph window. In the terminal, you should see:

BFS Path: Hospital -> Downtown_A -> Downtown_B -> Emergency_Site
Hops: 3, Travel time: 37 minutes

BFS found the 3-hop path through congested downtown because it only counted edges. It has no idea that this route takes 37 minutes of travel time through heavy traffic. A highway route exists that takes far less time, but BFS ignored it because it requires more hops.

Why is this a problem?

For an ambulance, 37 minutes could cost a life. BFS is blind to edge weights. It found the "shortest" path by its own metric (fewest hops), but that is the wrong metric for emergency routing.

This is the core lesson: algorithm choice depends on what "shortest" means in your problem. Fewest steps and lowest cost are different questions that need different algorithms.

Not seeing the expected output?

• If you see None instead of a path, check that the node names in your main block match exactly: "Hospital" and "Emergency_Site" (case-sensitive, with underscore).
• If travel time shows 0, make sure calculate_path_time accesses graph[path[i]][path[i + 1]]["weight"] with the key "weight" in quotes.

Help me debug my BFS output

✔️ Awesome, I've got everything!

Great. Double check you've saved emergency_router.py and confirmed the BFS output matches what's shown above.

ⓧ I'd like to double check the full code

Scroll up and confirm your file contains these sections in order:

• Imports at the top (networkx, matplotlib, deque, heapq).
• The # --- Graph Construction --- section with build_city_graph() and visualize_graph().
• The # --- BFS Pathfinding --- section with bfs_shortest_path() and calculate_path_time().
• The # --- Main --- section with the if __name__ == "__main__": block that builds the graph, visualizes it, runs BFS, and prints the result.

Your BFS implementation works, but it just told an ambulance to take a 37-minute route through congested downtown. Next up, you'll implement Dijkstra's algorithm to find the genuinely fastest path by considering edge weights.

Implement Dijkstra's Algorithm

In the last step, BFS found a route from Hospital to Emergency_Site in just 3 hops. That sounds efficient until you check the travel time: 37 minutes through congested downtown streets.

A highway route exists that takes only 17 minutes. Those 20 lost minutes could cost a life. Dijkstra's algorithm fixes this by considering edge weights, always expanding the node with the lowest total distance first.

In this step, get ready to:

• Implement Dijkstra's algorithm from scratch using a priority queue.
• Compare both algorithms side by side and validate against NetworkX's built-in.
• Visualize both routes overlaid on the same graph.

Implement Dijkstra's algorithm from scratch

Dijkstra's algorithm works differently from BFS. Instead of a simple first-in-first-out queue, it uses a priority queue that always processes the node with the smallest known distance next.

• In emergency_router.py, find the calculate_path_time function.
• Below it, add a section comment # --- Dijkstra's Algorithm --- on its own line, leave a blank line, then paste the exploration logic below:

def dijkstra_shortest_path(graph, start, goal):
    """Find shortest weighted path using Dijkstra's algorithm."""
    distances = {node: float("inf") for node in graph.nodes()}
    distances[start] = 0

    previous = {node: None for node in graph.nodes()}

    priority_queue = [(0, start)]
    visited = set()

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_node in visited:
            continue
        visited.add(current_node)

        if current_node == goal:
            break

        for neighbor in graph.neighbors(current_node):
            if neighbor in visited:
                continue
            edge_weight = graph[current_node][neighbor]["weight"]
            new_distance = current_distance + edge_weight

            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                previous[neighbor] = current_node
                heapq.heappush(priority_queue, (new_distance, neighbor))

What does this code do?

• distances tracks the shortest known distance from the start to every node. Everything starts at infinity except the start node (distance 0).
• previous records which node we came from to reach each node. This lets us reconstruct the path later.
• heapq.heappop always gives us the node with the smallest distance. This is the key difference from BFS, which processes nodes in the order they were discovered.
• The inner loop "relaxes" each edge. If going through the current node offers a shorter path to a neighbor, it updates the distance and pushes the neighbor onto the queue.

• Still inside the dijkstra_shortest_path function, add the path reconstruction logic directly below the while loop (at the same indentation level as the while keyword):

    path = []
    node = goal
    while node is not None:
        path.append(node)
        node = previous[node]
    path.reverse()

    if path[0] != start:
        return None
    return path

How does path reconstruction work?

The algorithm builds the path backwards. Starting from the goal, it follows the previous pointers back to the start. Then it reverses the list to get the path in the correct order.

If the first node in the reconstructed path is not the start, it means no path exists (we return None).

• Save emergency_router.py.
• Confirm there are no syntax errors by running this import test:

python -c "import emergency_router"

You should see the graph visualization appear (from the existing __main__ block) and the BFS output, with no errors about the new function.

Seeing a SyntaxError or IndentationError?

• Make sure the path reconstruction code is indented at one level inside the function (4 spaces), not inside the while loop (8 spaces).
• Check that the while priority_queue: loop and the path = [] line are at the same indentation level.
• Confirm you have a blank line between the section comment and the def line.

Why is my Dijkstra function causing a syntax error?

Run Dijkstra and compare to BFS

Now you need a function that runs both algorithms on the same route and prints the results side by side. This function also validates your implementation against NetworkX's built-in Dijkstra.

• Below your dijkstra_shortest_path function, paste the comparison function:

# --- Comparison and Visualization ---

def compare_algorithms(G, start, goal):
    """Compare BFS and Dijkstra results."""
    bfs_path = bfs_shortest_path(G, start, goal)
    dij_path = dijkstra_shortest_path(G, start, goal)

    bfs_time = calculate_path_time(G, bfs_path)
    dij_time = calculate_path_time(G, dij_path)

    print("=" * 50)
    print(f"Route: {start} -> {goal}")
    print("=" * 50)
    print(f"\nBFS Path (fewest hops):    {' -> '.join(bfs_path)}")
    print(f"  Hops: {len(bfs_path) - 1}, Travel time: {bfs_time} minutes")
    print(f"\nDijkstra Path (fastest):   {' -> '.join(dij_path)}")
    print(f"  Hops: {len(dij_path) - 1}, Travel time: {dij_time} minutes")
    print(f"\nTime saved by Dijkstra: {bfs_time - dij_time} minutes")

    nx_path = nx.dijkstra_path(G, start, goal, weight="weight")
    assert dij_path == nx_path, "Mismatch with NetworkX!"
    print("\nValidation: Your Dijkstra matches NetworkX's built-in! Correct!")

What does this code do?

• It runs both BFS and Dijkstra on the same start/goal pair and prints the paths, hop counts, and travel times.
• nx.dijkstra_path() is NetworkX's optimized Dijkstra. The assert statement crashes the script if your result doesn't match. If it passes, your implementation is correct.

• In emergency_router.py, scroll down to the if __name__ == "__main__": block at the bottom.
• Find this code:

if __name__ == "__main__":
    city = build_city_graph()
    visualize_graph(city)
    bfs_path = bfs_shortest_path(city, "Hospital", "Emergency_Site")
    bfs_time = calculate_path_time(city, bfs_path)
    print(f"BFS Path: {' -> '.join(bfs_path)}")
    print(f"Hops: {len(bfs_path) - 1}, Travel time: {bfs_time} minutes")

• Replace the entire __main__ block with this:

if __name__ == "__main__":
    city = build_city_graph()
    visualize_graph(city)
    compare_algorithms(city, "Hospital", "Emergency_Site")

• Save emergency_router.py.

Before you run this, what path do you think Dijkstra will find? Will it take the same downtown route as BFS, or a different one?

• Run the script:

python emergency_router.py

After the graph window appears (close it to continue), you should see output like this:

==================================================
Route: Hospital -> Emergency_Site
==================================================

BFS Path (fewest hops):    Hospital -> Downtown_A -> Downtown_B -> Emergency_Site
  Hops: 3, Travel time: 37 minutes

Dijkstra Path (fastest):   Hospital -> Highway_On -> Highway_1 -> Highway_2 -> Highway_Off -> Emergency_Site
  Hops: 5, Travel time: 17 minutes

Time saved by Dijkstra: 20 minutes

Validation: Your Dijkstra matches NetworkX's built-in! Correct!

Dijkstra found the highway route. It takes more hops (5 instead of 3) but only 17 minutes instead of 37. Your implementation matches NetworkX's built-in, confirming it is correct.

Why does BFS fail here?

BFS treats every edge as equal cost. It found the path with the fewest hops (3), but those 3 hops go through heavily congested downtown roads (15 + 12 + 10 = 37 minutes).

Dijkstra considers the actual travel time on each road. It discovers that 5 hops along fast highways (3 + 4 + 3 + 4 + 3 = 17 minutes) beats 3 hops through traffic. This is why algorithm choice matters for real routing problems.

Seeing an AssertionError?

• The assertion means your Dijkstra found a different path than NetworkX's. Double-check that you are updating distances[neighbor] only when new_distance < distances[neighbor].
• Make sure you skip neighbors already in the visited set.
• Confirm the edge weight is read from graph[current_node][neighbor]["weight"], not hardcoded.

Why is my Dijkstra result not matching NetworkX?

Visualize both paths on the same graph

Numbers tell one story. A visual comparison tells it instantly. You will draw both the BFS path and the Dijkstra path on the same graph so the difference is impossible to miss.

• In emergency_router.py, below the compare_algorithms function, paste the first part of the visualization function:

def visualize_comparison(G, bfs_path, dij_path, start, goal):
    """Draw both paths on the same graph."""
    pos = nx.spring_layout(G, seed=42)

    plt.figure(figsize=(14, 9))

    nx.draw_networkx_nodes(G, pos, node_size=700, node_color="lightgray")
    nx.draw_networkx_labels(G, pos, font_size=8, font_weight="bold")
    nx.draw_networkx_edges(G, pos, width=1, alpha=0.3, style="dashed")

    edge_labels = nx.get_edge_attributes(G, "weight")
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=7)

    bfs_edges = list(zip(bfs_path[:-1], bfs_path[1:]))
    nx.draw_networkx_edges(
        G, pos, edgelist=bfs_edges, width=3,
        edge_color="red", alpha=0.7, label="BFS (fewest hops)"
    )

    dij_edges = list(zip(dij_path[:-1], dij_path[1:]))
    nx.draw_networkx_edges(
        G, pos, edgelist=dij_edges, width=3,
        edge_color="green", alpha=0.7, label="Dijkstra (fastest)"
    )

What does this code do?

• It draws the full city graph in light gray as a backdrop, then overlays the BFS path in red and the Dijkstra path in green.
• zip(path[:-1], path[1:]) converts a list of nodes into pairs of consecutive edges so Matplotlib can draw them.

• Directly below (still inside the same function), paste the node highlights and save logic:

    nx.draw_networkx_nodes(
        G, pos, nodelist=[start], node_size=900,
        node_color="blue", alpha=0.7
    )
    nx.draw_networkx_nodes(
        G, pos, nodelist=[goal], node_size=900,
        node_color="orange", alpha=0.7
    )

    plt.legend(fontsize=12)
    plt.title(f"BFS vs Dijkstra: {start} to {goal}", fontsize=14)
    plt.axis("off")
    plt.tight_layout()
    plt.savefig("route_comparison.png", dpi=150, bbox_inches="tight")
    plt.show()
    print("Comparison saved to route_comparison.png")

What does this code do?

• The start node (Hospital) is highlighted in blue and the goal node (Emergency_Site) in orange so they stand out.
• The figure is saved to route_comparison.png and displayed in a window. The legend labels each colored path.

• Now scroll back up to the end of your compare_algorithms function.
• Find this line (the last line inside the function):

    print("\nValidation: Your Dijkstra matches NetworkX's built-in! Correct!")

• Add the following line directly below it, at the same indentation level:

    visualize_comparison(G, bfs_path, dij_path, start, goal)

• Save emergency_router.py.

Before you run, what do you expect the comparison image to show? Think about which path goes through downtown and which takes the highway.

• Run the script:

python emergency_router.py

After closing the first graph window, you should see the comparison output in your terminal. Then a second window opens showing both routes overlaid on the city map: the BFS path in red cutting through downtown, and the Dijkstra path in green looping along the highway.

Close the window and check your folder. You should see route_comparison.png saved alongside city_graph.png.

Seeing a NameError for visualize_comparison?

• Make sure visualize_comparison is defined ABOVE the if __name__ == "__main__": block but BELOW compare_algorithms.
• Check that the function name is spelled exactly visualize_comparison in both the definition and the call inside compare_algorithms.

Why is my visualize_comparison function not found?

✔️ Awesome, I've got everything!

Great. Double check you have saved emergency_router.py and that route_comparison.png appears in your project folder.

ⓧ I'd like to double check the full code

Your emergency_router.py file is now over 130 lines. Scroll through and confirm you have these sections in order:

• Imports (networkx, matplotlib, deque, heapq) at the top.
• # --- Graph Construction --- section with build_city_graph and visualize_graph.
• # --- BFS Pathfinding --- section with bfs_shortest_path and calculate_path_time.
• # --- Dijkstra's Algorithm --- section with dijkstra_shortest_path.
• # --- Comparison and Visualization --- section with compare_algorithms and visualize_comparison.
• # --- Main --- section calling build_city_graph(), visualize_graph(city), and compare_algorithms(city, "Hospital", "Emergency_Site").

Secret mission

Implement A* Search

Dijkstra finds the optimal path, but it explores in all directions equally. What if you could give the algorithm a sense of direction? A* uses a heuristic to guide the search toward the goal, visiting fewer nodes while still guaranteeing the optimal result. This is how real GPS navigation systems work.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your resources running, pause them to come back later, or delete them entirely.

Resources you used:

• The emergency-router project folder on your Desktop (contains emergency_router.py, city_graph.png, route_comparison.png, and the venv virtual environment).

Keep everything running

No action needed. Choose this if you're still actively building or want to experiment with different graph structures and algorithms.

• Your emergency-router folder stays on your Desktop with all code and images intact.
• To reactivate the virtual environment later, open a terminal in the emergency-router folder and run venv\Scripts\activate (Windows) or source venv/bin/activate (macOS/Linux).

Pause - I'll come back to this later

Deactivate the virtual environment to free up your terminal session. Your files remain on disk for next time.

• Run deactivate in your terminal to exit the virtual environment.
• Your project folder and all generated images remain on your Desktop.

Delete - I don't want to use this again

Remove all project files and start fresh. This deletes your code, generated images, and the virtual environment with its installed packages.

• Deactivate the virtual environment first by running deactivate in your terminal.
• Delete the project folder by running the command for your operating system.

macOS

cd ~/Desktop
rm -rf emergency-router

Windows

cd ~\Desktop
rmdir /s /q emergency-router

• Confirm the folder is gone by running ls (macOS) or dir (Windows) on your Desktop. You should no longer see emergency-router in the output.

Nice Work!

Nice Work!

Nice work! You just built a complete emergency response routing system that models a city as a weighted graph and proves why algorithm choice can be the difference between life and death.

You've learned how to:

• Model a real-world routing problem as a weighted graph using NetworkX, and implement BFS from scratch to discover its blind spot: it ignores edge weights entirely.
• Implement Dijkstra's algorithm from scratch using a priority queue, cutting emergency response time from 37 to 17 minutes.
• Validate your own algorithm implementation against NetworkX's built-in and visualize both routes side-by-side with Matplotlib, proving that algorithm choice has real-world consequences.
• Secret Mission: Implemented A* search with a Euclidean distance heuristic, learning how domain knowledge accelerates pathfinding while exploring fewer nodes than Dijkstra.

Ready to quiz yourself?