Flight Route Planner with Python

Build a flight route planner using graphs, BFS, DFS, and Dijkstra from scratch.

Introduction

30 Second Summary

Every time you search for flights, you're making a tradeoff between fewer layovers and a lower price. The way computers solve this is by modeling cities as connected points and testing different routes to find the best one.

In this project, you will build a flight route planner in Python that finds optimal routes using three different algorithms. You'll implement every data structure from scratch, building the exact patterns that Google tests most heavily in coding interviews.

What You'll Build

A flight route planning system built in Google Colab that models cities as a graph and finds optimal routes using three different algorithms.

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

  • A working graph built from scratch using Python's dict as an adjacency list to model flight routes between cities.
  • BFS and DFS implementations that find the shortest path and enumerate all possible routes.
  • A custom min-heap built from scratch and Dijkstra's algorithm for finding the cheapest route without using any library imports.
  • Secret Mission: Add a "max layovers" constraint to Dijkstra, solving the classic "Cheapest Flights Within K Stops" interview pattern.

Are there any prerequisites?

You'll need a Google account with access to Google Colab. Basic Python comfort (loops, functions, classes) is helpful.

Set Up Your Colab Notebook

Every data structure you build in this project runs in a single browser tab. No local installations, no package managers, no environment headaches.

Google Colab gives you a free Python notebook connected to Google's servers. In this step, you will create your notebook, confirm the Python runtime, and add the one import you are allowed to use.

In this step, get ready to:
  • Create and rename a Colab notebook.
  • Verify the Python 3.12 runtime is active.
  • Add your single allowed import.
Create a new notebook
  • Open your browser and navigate to colab.research.google.com.
  • Sign in with your Google account if prompted.
  • Click File in the top menu bar.
  • Click New notebook.
  • A blank notebook opens with a default name like Untitled0.ipynb at the top left.
  • Click the notebook title at the top left.
  • Replace the default name with Flight Route Planner - DSA and press Enter.

Why Colab for this project?

Colab runs Python on Google's servers and saves your notebook to Google Drive automatically. You get a consistent environment without installing anything locally.

For interview prep, this means you can focus entirely on the algorithms instead of fighting your local setup.

Verify your Python version

Colab provides a managed Python runtime. You need to confirm it is running Python 3.12, which supports the f-string syntax and standard library features you will use throughout this project.

  • Click into the first code cell (it has a play button on the left).
  • Check your Python version by typing the following code and pressing Shift+Enter to run it:
import sys
print(f"Python version: {sys.version}")

What does this code do?

import sys loads Python's built-in system module. sys.version holds a string describing the exact Python version running on this machine.

You should see output starting with Python version: 3.12 followed by additional version details.

Seeing a different Python version?

Colab manages the runtime for you, so you cannot install a different Python version. If you see 3.12, you are good to go. If you see a different major version, your Colab runtime may have been updated.

The code in this project works with Python 3.10 and above, so any 3.10+ version is fine.

help me troubleshoot my Colab Python version

Set up your imports cell

For this project, you will build every data structure from scratch. The one exception is Python's deque from the standard library, which provides the efficient queue you need for BFS.

  • Click on the code cell that contains your version check.
  • Select all the text in the cell and delete it.
  • Replace it with this import by typing the following code:
from collections import deque
  • Press Shift+Enter to run the cell.

Why only this one import?

In a Google interview, using collections.deque for a BFS queue is expected and standard. It gives O(1) append and popleft operations, which is exactly what a queue needs.

You are intentionally NOT importing heapq. The heap is the data structure being tested. Building it from scratch proves you understand the heap property, heapify operations, and O(log n) guarantees.

The cell runs silently with no output. This is correct. A successful import produces no visible result.

Seeing an ImportError?

collections is part of Python's standard library and is always available. If you see an error, check for typos in the import line. Make sure it reads exactly from collections import deque with no capital letters.

help me fix my import error in Colab

✔️ Awesome, I've got everything!

Great. Make sure the cell ran without errors and you see a green checkmark or a number to the left of the cell.

ⓧ I'd like to double check the full code

Your notebook should have one code cell containing exactly this:

from collections import deque

Your environment is ready. Next up, you will build the flight network graph from scratch using a Python dict as your adjacency list.

Build the Graph

Your Colab notebook is ready with Python confirmed and your single import in place. Now it's time to build the core data structure that every graph problem at Google starts with: the adjacency list.

An adjacency list represents a graph as a mapping from each node to its list of neighbors. In Python, a dict is the perfect structure for this because it gives you O(1) lookups by city name. Each key is a city, and each value is a list of destinations you can fly to from that city, paired with the flight cost.

In this step, get ready to:
  • Build a FlightGraph class using a dict-based adjacency list.
  • Populate the graph with 7 cities and 11 directed flight routes.
  • Understand why this representation is the one Google interviewers expect.
Implement the FlightGraph class

A directed, weighted graph means edges have a direction (NYC to LAX is not the same as LAX to NYC) and each edge has a cost. The Python dict acts as a hash map under the hood, giving you constant-time average lookups for any city.

  • Click into a new code cell below your import cell.
  • Add the following FlightGraph class:
class FlightGraph:
    """Directed weighted graph using adjacency list (dict-based hash map)."""

    def __init__(self):
        self.graph = {}

    def add_city(self, city):
        if city not in self.graph:
            self.graph[city] = []

    def add_route(self, origin, destination, cost):
        self.add_city(origin)
        self.add_city(destination)
        self.graph[origin].append((destination, cost))

    def get_neighbors(self, city):
        return self.graph.get(city, [])

    def get_cities(self):
        return list(self.graph.keys())

    def __str__(self):
        lines = []
        for city, routes in self.graph.items():
            destinations = [f"{dest}(${cost})" for dest, cost in routes]
            lines.append(f"  {city} -> {', '.join(destinations)}")
        return "Flight Network:\n" + "\n".join(lines)

What does this code do?

  • self.graph = {} initializes an empty dict. This IS the adjacency list. Keys are cities, values are lists of (destination, cost) tuples.
  • add_city only adds a city if it doesn't already exist. This prevents overwriting a city's route list.
  • add_route ensures both cities exist, then appends the route to the origin's neighbor list. It only adds one direction (origin to destination), making this a directed graph.
  • get_neighbors uses .get(city, []) to safely return an empty list for unknown cities instead of crashing.
  • Run this cell by pressing the play button (or Shift+Enter).

You won't see any output. The class definition loads silently into memory for the next cell to use.

Seeing a syntax error?

  • Check your indentation. Python requires consistent spacing. Every method inside the class must be indented one level (4 spaces), and the code inside each method must be indented two levels (8 spaces).
  • Make sure the f-strings in the __str__ method use double quotes on the outside and single quotes (or escaped quotes) on the inside. Mismatched quotes are a common cause of syntax errors.

Help me fix a syntax error in my FlightGraph class definition.

✔️ Awesome, I've got everything!

Great. Make sure the cell has run without errors before moving on.

ⓧ I'd like to double check the full code

class FlightGraph:
    """Directed weighted graph using adjacency list (dict-based hash map)."""

    def __init__(self):
        self.graph = {}

    def add_city(self, city):
        if city not in self.graph:
            self.graph[city] = []

    def add_route(self, origin, destination, cost):
        self.add_city(origin)
        self.add_city(destination)
        self.graph[origin].append((destination, cost))

    def get_neighbors(self, city):
        return self.graph.get(city, [])

    def get_cities(self):
        return list(self.graph.keys())

    def __str__(self):
        lines = []
        for city, routes in self.graph.items():
            destinations = [f"{dest}(${cost})" for dest, cost in routes]
            lines.append(f"  {city} -> {', '.join(destinations)}")
        return "Flight Network:\n" + "\n".join(lines)
Populate the flight network

Now you will create a network of 7 cities connected by 11 directed routes with varying costs. The costs are deliberately chosen so that the shortest path by hops is NOT always the cheapest. This will matter when you compare BFS and Dijkstra later.

  • Click into a new code cell below your FlightGraph class.
  • Add the following code to build and print the flight network:
planner = FlightGraph()

routes = [
    ("NYC", "LAX", 400),
    ("NYC", "CHI", 150),
    ("NYC", "MIA", 200),
    ("CHI", "LAX", 100),
    ("CHI", "DEN", 180),
    ("LAX", "SFO", 100),
    ("LAX", "SEA", 150),
    ("DEN", "SFO", 250),
    ("DEN", "SEA", 300),
    ("MIA", "LAX", 350),
    ("SFO", "SEA", 80),
]

for origin, dest, cost in routes:
    planner.add_route(origin, dest, cost)

print(planner)
print(f"\nCities: {planner.get_cities()}")
print(f"Routes from NYC: {planner.get_neighbors('NYC')}")

What does this code do?

  • planner = FlightGraph() creates an instance of your graph. This is the object you will pass to BFS, DFS, and Dijkstra in later steps.
  • The routes list stores all 11 directed edges as (origin, destination, cost) tuples. Notice NYC to LAX costs $400, but NYC to CHI is only $150 and CHI to LAX is $100. That cheaper indirect path is what Dijkstra will find later.
  • The for loop unpacks each tuple and calls add_route to insert every edge into the graph.
  • Run this cell by pressing Shift+Enter.
  • You should see the full flight network printed with all 7 cities and their outgoing routes. The last line should show Routes from NYC: followed by 3 tuples (LAX, CHI, and MIA with their costs).

Seeing a NameError for FlightGraph?

  • This means Cell 2 (the class definition) hasn't been run yet. Go back to Cell 2 and run it first, then run Cell 3 again.
  • In Colab, cells must be run in order. If you restarted the runtime, you need to re-run all previous cells from the top.

Help me fix my FlightGraph network output.

✔️ Awesome, I've got everything!

Great. You should see all 7 cities and 11 routes in the output. Make sure the NYC neighbors line shows 3 tuples.

ⓧ I'd like to double check the full code

planner = FlightGraph()

routes = [
    ("NYC", "LAX", 400),
    ("NYC", "CHI", 150),
    ("NYC", "MIA", 200),
    ("CHI", "LAX", 100),
    ("CHI", "DEN", 180),
    ("LAX", "SFO", 100),
    ("LAX", "SEA", 150),
    ("DEN", "SFO", 250),
    ("DEN", "SEA", 300),
    ("MIA", "LAX", 350),
    ("SFO", "SEA", 80),
]

for origin, dest, cost in routes:
    planner.add_route(origin, dest, cost)

print(planner)
print(f"\nCities: {planner.get_cities()}")
print(f"Routes from NYC: {planner.get_neighbors('NYC')}")
Understand the interview mental model

Google interviewers expect you to articulate WHY you chose a specific data structure. Here are the three questions they would ask about your FlightGraph, along with the answers you should internalize.

Why adjacency list over adjacency matrix?

A flight network is a sparse graph. 7 cities could have up to 42 directed edges (7 x 6), but you only have 11. An adjacency matrix would allocate O(V²) space (a 7x7 grid of mostly zeros). Your adjacency list uses only O(V + E) space, storing just the edges that actually exist.

For sparse real-world graphs (social networks, flight routes, web pages), adjacency lists are almost always the right choice.

Why a dict and not a list?

A Python dict gives you O(1) average-case lookup by city name. If you used a list, you would need a separate mapping from city names to integer indices. The dict eliminates that extra step and makes the code more readable.

What is the time complexity of checking if a route exists?

To check if a route exists from city A to city B, you look up A in O(1), then scan A's neighbor list. That scan is O(degree of A). For most graphs, the degree is much smaller than V, making this efficient in practice.

Key complexities to memorize

  • Adding a city: O(1) average (dict insertion).
  • Adding a route: O(1) average (dict lookup + list append).
  • Getting neighbors: O(1) average (dict lookup).
  • Space: O(V + E) where V = cities and E = routes.

Your graph is built and verified. Next up, you will use BFS to find the shortest path between cities by counting hops. This is where the graph comes alive.

Implement BFS for Shortest Path

Your flight graph is built and populated with 7 cities and 11 routes. Now you need a way to answer the first query: "What is the shortest route from NYC to SFO by number of flights?"

BFS (Breadth-First Search) solves this by exploring all cities one hop away before any city two hops away. This level-by-level expansion guarantees the first time you reach a destination, you took the fewest flights to get there.

In this step, get ready to:
  • Implement BFS to find the shortest path by number of flights.
  • Implement BFS reachability to find all connected cities.
  • Test both functions and internalize time and space complexity.
Implement the BFS shortest path function

BFS uses a queue (FIFO) to explore nodes level by level. By storing the full path alongside each node in the queue, you can return the exact route the moment you reach the destination.

  • Click the + Code button below your existing cells to create a new code cell (Cell 4).
  • Add the BFS shortest path function by pasting this code:
def bfs_shortest_path(graph, start, end):
    """Find shortest path (fewest hops) using BFS."""
    if start not in graph.graph or end not in graph.graph:
        return None

    queue = deque([(start, [start])])
    visited = {start}

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

        if current == end:
            return path

        for neighbor, cost in graph.get_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])]) initializes a FIFO queue. Each entry is a tuple of the current city and the full path taken to reach it.
  • visited = {start} tracks which cities you have already explored. This prevents infinite cycles (e.g. if A connects to B and B connects to A).
  • queue.popleft() dequeues from the front (FIFO), guaranteeing level-by-level expansion. The first time you reach end, you have the fewest-hop path.
  • Do not run the cell yet. You will add more code below this function first.

Why does BFS guarantee the shortest path?

BFS explores all nodes at distance K before any node at distance K+1. The moment it reaches the destination, no shorter path can exist because every shorter-length path was already explored in an earlier level.

This is the fundamental insight interviewers want you to articulate. Time complexity is O(V + E). Space complexity is O(V).

Implement BFS reachability

The "connected component" pattern answers a different question: from a given city, which other cities can you reach at all? This is BFS without a target destination.

  • In the same cell (Cell 4), add this function below bfs_shortest_path:
def bfs_reachable(graph, start):
    """Find all cities reachable from start using BFS."""
    visited = {start}
    queue = deque([start])

    while queue:
        current = queue.popleft()
        for neighbor, cost in graph.get_neighbors(current):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return visited - {start}

What's different about this BFS?

This version does not track paths or check for a destination. It simply explores outward until the queue is empty, collecting every city it touches.

visited - {start} at the end removes the starting city from the result, since you want to know what is reachable from it, not include it.

  • Do not run the cell yet. You will add test code in the next substep.
Test and analyze the results

Now add test cases that exercise both functions on your flight network. These tests verify correctness and reveal the key insight about BFS: it optimizes for hops, not cost.

  • Below both functions in Cell 4, add the following test code:
# Test BFS
print("=== BFS: Shortest Path (Fewest Hops) ===\n")

path = bfs_shortest_path(planner, "NYC", "SFO")
print(f"NYC -> SFO: {' -> '.join(path)} ({len(path)-1} hops)")

path = bfs_shortest_path(planner, "NYC", "SEA")
print(f"NYC -> SEA: {' -> '.join(path)} ({len(path)-1} hops)")

path = bfs_shortest_path(planner, "CHI", "SEA")
print(f"CHI -> SEA: {' -> '.join(path)} ({len(path)-1} hops)")

print(f"\n=== BFS: Reachable Cities ===\n")

reachable = bfs_reachable(planner, "NYC")
print(f"From NYC: {reachable}")

reachable = bfs_reachable(planner, "SFO")
print(f"From SFO: {reachable}")

What do these tests check?

  • NYC to SFO tests a 2-hop path. BFS should find NYC -> LAX -> SFO.
  • NYC to SEA also tests a 2-hop path. BFS picks the fewest flights regardless of cost.
  • Reachability from NYC should show all 6 other cities. Reachability from SFO should show only SEA (since SFO only connects outward to SEA in this directed graph).
  • Run Cell 4 by pressing Shift+Enter or clicking the play button on the left.
  • You should see NYC -> SFO resolved as NYC -> LAX -> SFO (2 hops).
  • The reachable set from NYC should contain 6 cities. The reachable set from SFO should contain only SEA.

Seeing a NameError for deque or planner?

  • Make sure you ran Cells 1-3 earlier in this session. Colab loses all variables if the runtime disconnects. Re-run Cells 1, 2, and 3 in order, then run Cell 4 again.
  • Check that your function references graph.graph (accessing the dict attribute on the FlightGraph instance), not just graph.

Why is my BFS returning None or an incorrect path?

Why does BFS find NYC -> LAX -> SEA for NYC to SEA?

BFS picks the 2-hop path NYC -> LAX -> SEA ($550) even though a 3-hop path NYC -> CHI -> LAX -> SEA costs only $400. BFS does not look at costs. It stops the moment it reaches the destination at the shallowest level.

This is exactly why you will need Dijkstra's algorithm later. BFS optimizes hops. Dijkstra optimizes cost.

✔️ Awesome, I've got everything!

Great. Double check you see the correct output, then move on.

ⓧ I'd like to double check the full code

Here is the complete Cell 4. Make sure your code matches this exactly:

def bfs_shortest_path(graph, start, end):
    """Find shortest path (fewest hops) using BFS."""
    if start not in graph.graph or end not in graph.graph:
        return None

    queue = deque([(start, [start])])
    visited = {start}

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

        if current == end:
            return path

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

    return None


def bfs_reachable(graph, start):
    """Find all cities reachable from start using BFS."""
    visited = {start}
    queue = deque([start])

    while queue:
        current = queue.popleft()
        for neighbor, cost in graph.get_neighbors(current):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return visited - {start}


# Test BFS
print("=== BFS: Shortest Path (Fewest Hops) ===\n")

path = bfs_shortest_path(planner, "NYC", "SFO")
print(f"NYC -> SFO: {' -> '.join(path)} ({len(path)-1} hops)")

path = bfs_shortest_path(planner, "NYC", "SEA")
print(f"NYC -> SEA: {' -> '.join(path)} ({len(path)-1} hops)")

path = bfs_shortest_path(planner, "CHI", "SEA")
print(f"CHI -> SEA: {' -> '.join(path)} ({len(path)-1} hops)")

print(f"\n=== BFS: Reachable Cities ===\n")

reachable = bfs_reachable(planner, "NYC")
print(f"From NYC: {reachable}")

reachable = bfs_reachable(planner, "SFO")
print(f"From SFO: {reachable}")

You now have BFS working for shortest-by-hops queries. But you saw the limitation: BFS picks the 2-hop NYC -> LAX -> SEA ($550) when a cheaper 3-hop route exists. Next, you will use DFS to enumerate every possible path so you can see all options at once.

Implement DFS for All Paths

BFS found the shortest route by hop count. But a flight with fewer stops is not always the cheapest option. What if you want to see every possible route so you can compare them?

In this step, you will implement DFS with backtracking to enumerate all paths between two cities. You will then prove that the fewest-hop path is not always the cheapest, which is exactly why Dijkstra's algorithm exists.

In this step, get ready to:
  • Implement DFS with backtracking for all-paths enumeration.
  • Build a path cost calculator to compare route prices.
  • Compare DFS results with BFS to reveal why weighted shortest path matters.
Implement DFS with backtracking

BFS uses a queue and visits each node once. DFS takes a different approach. It dives as deep as possible along one path, then backtracks to try other branches.

The key insight for finding ALL paths: you must remove a city from the visited set after returning from the recursive call. This "backtracking" lets the algorithm explore other routes that pass through the same city.

  • Click + Code below your BFS cell to create a new code cell (Cell 5).
  • Add the dfs_all_paths function by pasting this code:
def dfs_all_paths(graph, start, end, max_length=6):
    """Find ALL paths from start to end using DFS with backtracking."""
    all_paths = []

    def dfs(current, path, visited):
        if len(path) > max_length:
            return

        if current == end:
            all_paths.append(list(path))
            return

        for neighbor, cost in graph.get_neighbors(current):
            if neighbor not in visited:
                visited.add(neighbor)
                path.append(neighbor)
                dfs(neighbor, path, visited)
                path.pop()
                visited.remove(neighbor)

    dfs(start, [start], {start})
    return all_paths

What does this code do?

The outer function dfs_all_paths sets up a results list and kicks off a recursive inner function dfs.

  • max_length=6 prevents the algorithm from exploring unreasonably long paths in large graphs.
  • When current == end, the path is complete. list(path) saves a copy (not a reference) to all_paths.
  • The backtracking pair (path.pop() and visited.remove(neighbor)) undoes each choice after the recursive call returns, letting the algorithm try the next neighbor.

Why backtracking instead of a simple visited set?

In BFS, you mark a node visited permanently because you only need the shortest path. In DFS all-paths, a city might appear in multiple valid routes. Removing it from visited after each recursive return lets the algorithm discover every combination.

This is the same backtracking pattern Google tests in permutation, combination, and constraint-satisfaction problems.

Do not run the cell yet. You will add the cost calculator next and run them together.

Implement the path cost calculator

DFS finds routes, but it does not track cost along the way. You need a helper function that takes a completed path and sums up the edge weights.

  • In the same cell (Cell 5), add the path_cost function directly below dfs_all_paths:
def path_cost(graph, path):
    """Calculate total cost of a path."""
    total = 0
    for i in range(len(path) - 1):
        for neighbor, cost in graph.get_neighbors(path[i]):
            if neighbor == path[i + 1]:
                total += cost
                break
    return total

What does this code do?

For each consecutive pair of cities in the path, it looks up the edge weight from the graph's adjacency list. The break exits the inner loop as soon as the matching neighbor is found, avoiding unnecessary iteration.

Time complexity is O(P * D) where P is the path length and D is the average degree (number of outgoing routes) of each city.

Test and compare with BFS

Now for the payoff. You will run DFS on two routes and compare the results against what BFS found in the previous step.

  • Still in Cell 5, add this test code below path_cost:
# Test DFS
print("=== DFS: All Possible Routes ===\n")

paths = dfs_all_paths(planner, "NYC", "SFO")
print(f"All routes NYC -> SFO ({len(paths)} found):")
for p in paths:
    cost = path_cost(planner, p)
    print(f"  {' -> '.join(p)} | Cost: ${cost} | Hops: {len(p)-1}")

print()

paths = dfs_all_paths(planner, "NYC", "SEA")
print(f"All routes NYC -> SEA ({len(paths)} found):")
for p in paths:
    cost = path_cost(planner, p)
    print(f"  {' -> '.join(p)} | Cost: ${cost} | Hops: {len(p)-1}")

What does this code do?

It runs dfs_all_paths on two city pairs (NYC to SFO and NYC to SEA), then prints every discovered route with its total cost and hop count.

This lets you visually compare all options and see that fewer hops does not guarantee a lower price.

  • Run Cell 5 by pressing Shift+Enter.

You should see multiple routes for each city pair. Look at the NYC to SFO results. The BFS path from the previous step was NYC -> LAX -> SFO (2 hops, $500). DFS reveals that NYC -> CHI -> LAX -> SFO takes 3 hops but only costs $350.

Why does this matter for interviews?

This comparison is the entire motivation for Dijkstra's algorithm. BFS optimizes for hops (unweighted). Dijkstra optimizes for cost (weighted). An interviewer will ask you to articulate exactly this distinction.

The DFS all-paths pattern itself appears in Google problems like "all paths from source to target" where you enumerate every valid route through a directed graph.

Seeing an empty list or missing paths?

  • Make sure you ran Cell 3 (the network builder) before Cell 5. The planner variable must exist in memory.
  • Check that dfs_all_paths and path_cost are both in Cell 5 above the test code. Python reads top to bottom.
  • If you see only 1-2 paths instead of 4+, check that the backtracking lines (path.pop() and visited.remove(neighbor)) are inside the for loop, at the same indentation as dfs(neighbor, path, visited).

Help me debug my DFS backtracking implementation

✔️ Awesome, I've got everything!

Double check you have all three pieces in Cell 5: dfs_all_paths, path_cost, and the test code.

ⓧ I'd like to double check the full code

Here is the complete Cell 5 for comparison:

def dfs_all_paths(graph, start, end, max_length=6):
    """Find ALL paths from start to end using DFS with backtracking."""
    all_paths = []

    def dfs(current, path, visited):
        if len(path) > max_length:
            return

        if current == end:
            all_paths.append(list(path))
            return

        for neighbor, cost in graph.get_neighbors(current):
            if neighbor not in visited:
                visited.add(neighbor)
                path.append(neighbor)
                dfs(neighbor, path, visited)
                path.pop()
                visited.remove(neighbor)

    dfs(start, [start], {start})
    return all_paths


def path_cost(graph, path):
    """Calculate total cost of a path."""
    total = 0
    for i in range(len(path) - 1):
        for neighbor, cost in graph.get_neighbors(path[i]):
            if neighbor == path[i + 1]:
                total += cost
                break
    return total


# Test DFS
print("=== DFS: All Possible Routes ===\n")

paths = dfs_all_paths(planner, "NYC", "SFO")
print(f"All routes NYC -> SFO ({len(paths)} found):")
for p in paths:
    cost = path_cost(planner, p)
    print(f"  {' -> '.join(p)} | Cost: ${cost} | Hops: {len(p)-1}")

print()

paths = dfs_all_paths(planner, "NYC", "SEA")
print(f"All routes NYC -> SEA ({len(paths)} found):")
for p in paths:
    cost = path_cost(planner, p)
    print(f"  {' -> '.join(p)} | Cost: ${cost} | Hops: {len(p)-1}")

You now have two traversal algorithms. BFS finds the fewest hops. DFS finds every possible route. But neither one directly answers "what is the cheapest path?" Next up, you will build a MinHeap from scratch and implement Dijkstra's algorithm to answer that question optimally.

Build MinHeap and Dijkstra's Algorithm

Your DFS results from the last step revealed something important. The fewest-hop path is not always the cheapest path. NYC to SFO in 2 hops costs $500, but taking 3 hops through Chicago costs only $350.

To find the actual cheapest route, you need an algorithm that accounts for edge weights. That algorithm is Dijkstra's algorithm. It relies on a priority queue (min-heap) to always process the lowest-cost option next. In this step, you will build both the heap and the algorithm from scratch.

In this step, get ready to:
  • Build a MinHeap class from scratch with O(log n) push and pop.
  • Implement Dijkstra's algorithm using your custom MinHeap.
  • Compare BFS and Dijkstra results to see when they disagree.
Implement MinHeap from scratch

A min-heap is a binary tree stored as an array where the parent is always smaller than both children. This guarantees the minimum element is always at index 0, giving you O(1) peek and O(log n) insertion and removal.

In a Google interview, building a heap from scratch proves you understand the data structure behind priority queues. Python has heapq in the standard library, but using it in an interview misses the point. The interviewer wants to see you implement the heap property.

  • Create a new code cell below Cell 5 by clicking the + Code button.
  • Add the MinHeap class by pasting this code:
class MinHeap:
    """Min-heap implementation from scratch (no heapq)."""

    def __init__(self):
        self.heap = []

    def _parent(self, i):
        return (i - 1) // 2

    def _left_child(self, i):
        return 2 * i + 1

    def _right_child(self, i):
        return 2 * i + 2

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def _heapify_up(self, i):
        while i > 0 and self.heap[i][0] < self.heap[self._parent(i)][0]:
            self._swap(i, self._parent(i))
            i = self._parent(i)

    def _heapify_down(self, i):
        size = len(self.heap)
        smallest = i

        left = self._left_child(i)
        right = self._right_child(i)

        if left < size and self.heap[left][0] < self.heap[smallest][0]:
            smallest = left
        if right < size and self.heap[right][0] < self.heap[smallest][0]:
            smallest = right

        if smallest != i:
            self._swap(i, smallest)
            self._heapify_down(smallest)

    def push(self, priority, value):
        self.heap.append((priority, value))
        self._heapify_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            return None

        root = self.heap[0]
        last = self.heap.pop()

        if self.heap:
            self.heap[0] = last
            self._heapify_down(0)

        return root

    def peek(self):
        return self.heap[0] if self.heap else None

    def is_empty(self):
        return len(self.heap) == 0

    def size(self):
        return len(self.heap)

What does this class do?

The heap stores tuples of (priority, value) in a flat list. The tree structure is implicit through index math.

  • _heapify_up runs after every push. It bubbles the new element upward until the parent is smaller.
  • _heapify_down runs after every pop. It sinks the replacement element downward until both children are larger.
  • push is O(log n) because the element travels at most the height of the tree. pop is also O(log n) for the same reason.

You won't see output yet. The next chunk adds test code to verify the heap works independently.

  • Add this test code directly below the MinHeap class in the same cell:
# Test the heap
print("=== Testing MinHeap ===\n")

heap = MinHeap()
test_data = [(5, "DEN"), (2, "CHI"), (8, "LAX"), (1, "NYC"), (4, "MIA")]

for priority, city in test_data:
    heap.push(priority, city)
    print(f"  Pushed ({priority}, {city}) | Heap size: {heap.size()}")

print(f"\n  Peek (min): {heap.peek()}")
print(f"\n  Popping in priority order:")

while not heap.is_empty():
    item = heap.pop()
    print(f"    {item}")

What does this test prove?

The test pushes 5 cities with out-of-order priorities (5, 2, 8, 1, 4) then pops them all. If your heap is correct, they come out in ascending priority order: 1, 2, 4, 5, 8. This proves the heap property holds through multiple insertions and deletions.

  • Run Cell 6 by pressing Shift+Enter.
  • You should see items popped in order: (1, 'NYC'), (2, 'CHI'), (4, 'MIA'), (5, 'DEN'), (8, 'LAX').

Items not popping in order?

  • Check that _heapify_up compares self.heap[i][0] (the priority at index 0 of the tuple), not the entire tuple.
  • Verify _heapify_down checks both left and right children before swapping. Missing the right-child check causes incorrect ordering.
  • Make sure pop replaces index 0 with the last element before calling _heapify_down. Popping the last element first (with self.heap.pop()) and then assigning it to index 0 is the correct order.

Help me debug my MinHeap. Items are not coming out in priority order.

✔️ Awesome, I've got everything!

Great. Make sure Cell 6 ran without errors and items popped in ascending order.

ⓧ I'd like to double check the full code

Here is the complete Cell 6 for comparison.

class MinHeap:
    """Min-heap implementation from scratch (no heapq)."""

    def __init__(self):
        self.heap = []

    def _parent(self, i):
        return (i - 1) // 2

    def _left_child(self, i):
        return 2 * i + 1

    def _right_child(self, i):
        return 2 * i + 2

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def _heapify_up(self, i):
        while i > 0 and self.heap[i][0] < self.heap[self._parent(i)][0]:
            self._swap(i, self._parent(i))
            i = self._parent(i)

    def _heapify_down(self, i):
        size = len(self.heap)
        smallest = i

        left = self._left_child(i)
        right = self._right_child(i)

        if left < size and self.heap[left][0] < self.heap[smallest][0]:
            smallest = left
        if right < size and self.heap[right][0] < self.heap[smallest][0]:
            smallest = right

        if smallest != i:
            self._swap(i, smallest)
            self._heapify_down(smallest)

    def push(self, priority, value):
        self.heap.append((priority, value))
        self._heapify_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            return None

        root = self.heap[0]
        last = self.heap.pop()

        if self.heap:
            self.heap[0] = last
            self._heapify_down(0)

        return root

    def peek(self):
        return self.heap[0] if self.heap else None

    def is_empty(self):
        return len(self.heap) == 0

    def size(self):
        return len(self.heap)


# Test the heap
print("=== Testing MinHeap ===\n")

heap = MinHeap()
test_data = [(5, "DEN"), (2, "CHI"), (8, "LAX"), (1, "NYC"), (4, "MIA")]

for priority, city in test_data:
    heap.push(priority, city)
    print(f"  Pushed ({priority}, {city}) | Heap size: {heap.size()}")

print(f"\n  Peek (min): {heap.peek()}")
print(f"\n  Popping in priority order:")

while not heap.is_empty():
    item = heap.pop()
    print(f"    {item}")
Implement Dijkstra's algorithm

Dijkstra's algorithm finds the cheapest path in a weighted graph. It works by always processing the lowest-cost unvisited node next. Your MinHeap makes this efficient because popping the minimum is O(log n) instead of O(n) with a naive scan.

How does Dijkstra's algorithm work?

The algorithm maintains a distance table with the cheapest known cost to reach each city. It starts at zero for the source and infinity for everything else.

On each iteration, it pops the cheapest unvisited city from the heap, then checks all its neighbors. If traveling through the current city offers a cheaper route to a neighbor than previously known, it updates the distance and pushes the neighbor into the heap. This process is called "relaxing" an edge.

  • Create a new code cell below Cell 6.
  • Add the dijkstra function by pasting this code:
def dijkstra(graph, start, end):
    """Find cheapest route using Dijkstra's algorithm with custom MinHeap."""
    distances = {city: float('inf') for city in graph.get_cities()}
    distances[start] = 0
    previous = {city: None for city in graph.get_cities()}

    heap = MinHeap()
    heap.push(0, start)
    visited = set()

    while not heap.is_empty():
        current_dist, current = heap.pop()

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

        if current == end:
            break

        for neighbor, cost in graph.get_neighbors(current):
            if neighbor not in visited:
                new_dist = current_dist + cost
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    previous[neighbor] = current
                    heap.push(new_dist, neighbor)

    if distances[end] == float('inf'):
        return None, float('inf')

    path = []
    current = end
    while current is not None:
        path.append(current)
        current = previous[current]
    path.reverse()

    return path, distances[end]

What does this code do?

  • distances tracks the cheapest known cost to reach each city. Everything starts at infinity except the start city (0).
  • previous records which city we came from to reach each destination. This lets us reconstruct the path at the end.
  • The if current in visited: continue line skips stale heap entries. Since we push duplicates rather than updating in place, old entries with higher costs may linger in the heap.
  • The relaxation check if new_dist < distances[neighbor] only updates when a strictly cheaper path is found.
  • Time complexity is O((V + E) log V). Space is O(V).

You won't see output yet. The next chunk adds test code to verify the algorithm works.

Compare BFS vs Dijkstra

This is the core insight of the entire project. BFS optimizes for fewest hops. Dijkstra optimizes for lowest total cost. When edge weights vary, they give different answers.

  • Add this test and comparison code directly below the dijkstra function in the same cell:
# Test Dijkstra
print("=== Dijkstra: Cheapest Route ===\n")

test_routes = [
    ("NYC", "SFO"),
    ("NYC", "SEA"),
    ("CHI", "SEA"),
    ("NYC", "LAX"),
]

for start, end in test_routes:
    path, cost = dijkstra(planner, start, end)
    print(f"{start} -> {end}: {' -> '.join(path)} | Total: ${cost}")

# Compare BFS vs Dijkstra
print("\n=== Comparison: Fewest Hops vs Cheapest ===\n")

bfs_path = bfs_shortest_path(planner, "NYC", "SEA")
dij_path, dij_cost = dijkstra(planner, "NYC", "SEA")
bfs_cost = path_cost(planner, bfs_path)

print(f"BFS (fewest hops):   {' -> '.join(bfs_path)} | {len(bfs_path)-1} hops | ${bfs_cost}")
print(f"Dijkstra (cheapest): {' -> '.join(dij_path)} | {len(dij_path)-1} hops | ${dij_cost}")

What should I see?

The Dijkstra test shows the cheapest route for each city pair. The comparison section is the key output.

  • BFS picks NYC -> LAX -> SEA (2 hops, $550) because it minimizes the number of flights.
  • Dijkstra picks NYC -> CHI -> LAX -> SEA (3 hops, $400) because it minimizes total cost ($150 + $100 + $150 = $400).
  • This is why weighted shortest-path algorithms exist. Hop count and cost are different objectives.
  • Run Cell 7 by pressing Shift+Enter.
  • Confirm that the comparison shows BFS at $550 and Dijkstra at $400 for NYC to SEA.

Seeing infinity or no path found?

  • Make sure Cell 6 (MinHeap) was run before Cell 7. Dijkstra depends on the MinHeap class being defined.
  • Verify that Cells 2, 3, and 4 have already been run. Cell 7 uses planner, bfs_shortest_path, and path_cost from earlier cells.
  • Check that the relaxation condition uses new_dist < distances[neighbor] (strict less-than). Using <= causes unnecessary heap entries and can produce incorrect paths.

Help me debug my Dijkstra implementation. I am getting infinity or incorrect paths.

✔️ Awesome, I've got everything!

Great. Make sure Cell 7 ran without errors and the comparison shows Dijkstra finding a cheaper route than BFS.

ⓧ I'd like to double check the full code

Here is the complete Cell 7 for comparison.

def dijkstra(graph, start, end):
    """Find cheapest route using Dijkstra's algorithm with custom MinHeap."""
    distances = {city: float('inf') for city in graph.get_cities()}
    distances[start] = 0
    previous = {city: None for city in graph.get_cities()}

    heap = MinHeap()
    heap.push(0, start)
    visited = set()

    while not heap.is_empty():
        current_dist, current = heap.pop()

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

        if current == end:
            break

        for neighbor, cost in graph.get_neighbors(current):
            if neighbor not in visited:
                new_dist = current_dist + cost
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    previous[neighbor] = current
                    heap.push(new_dist, neighbor)

    if distances[end] == float('inf'):
        return None, float('inf')

    path = []
    current = end
    while current is not None:
        path.append(current)
        current = previous[current]
    path.reverse()

    return path, distances[end]


# Test Dijkstra
print("=== Dijkstra: Cheapest Route ===\n")

test_routes = [
    ("NYC", "SFO"),
    ("NYC", "SEA"),
    ("CHI", "SEA"),
    ("NYC", "LAX"),
]

for start, end in test_routes:
    path, cost = dijkstra(planner, start, end)
    print(f"{start} -> {end}: {' -> '.join(path)} | Total: ${cost}")

# Compare BFS vs Dijkstra
print("\n=== Comparison: Fewest Hops vs Cheapest ===\n")

bfs_path = bfs_shortest_path(planner, "NYC", "SEA")
dij_path, dij_cost = dijkstra(planner, "NYC", "SEA")
bfs_cost = path_cost(planner, bfs_path)

print(f"BFS (fewest hops):   {' -> '.join(bfs_path)} | {len(bfs_path)-1} hops | ${bfs_cost}")
print(f"Dijkstra (cheapest): {' -> '.join(dij_path)} | {len(dij_path)-1} hops | ${dij_cost}")

Secret mission

Cheapest Flights Within K Stops

Standard Dijkstra finds the absolute cheapest path with no constraints. But what if you can only take 2 layovers? Extend your algorithm with state expansion to solve the exact pattern Google tests in interviews.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely in Google Colab with no external packages or paid services. There are no ongoing costs.

Resources you used:

  • Google Colab notebook "Flight Route Planner - DSA" (saved automatically to Google Drive).

Keep everything running

No action needed. Choose this if you want to revisit the notebook for interview prep or extend it with new algorithms.

  • Your notebook stays in Google Drive for free. Open it anytime from colab.research.google.com.
  • Use the Share button in Colab to send a link to study partners or interviewers as a portfolio piece.

Pause - I'll come back to this later

Disconnect the Colab runtime to free up compute resources. Your notebook file remains safe in Google Drive.

  • In your Colab notebook, click Runtime in the top menu bar.
  • Click Disconnect and delete runtime.
  • Your code and outputs are saved. When you return, just click a cell and run it to reconnect.

Delete - I don't want to use this again

Remove the notebook entirely from your Google Drive.

  • Open Google Drive at drive.google.com.
  • Navigate to the Colab Notebooks folder.
  • Right-click on Flight Route Planner - DSA and select Move to trash.
  • Empty your trash to permanently delete the file.

That's a Wrap!

That's a Wrap!

Nice work! You just built a complete flight route planning system from scratch, implementing the exact graph algorithms and data structures that Google tests most heavily in coding interviews.

You've learned how to:

  • Build a directed weighted graph from scratch using a dict-based adjacency list, then implement BFS for shortest-by-hops paths and DFS with backtracking to enumerate every possible route.
  • Implement a MinHeap from scratch with O(log n) push/pop and use it to power Dijkstra's algorithm for finding the cheapest weighted path.
  • Demonstrate when BFS and Dijkstra give different answers, proving why weighted shortest-path algorithms exist even when an unweighted solution looks sufficient.
  • Secret Mission: Extended Dijkstra with state expansion (cost, city, stops) to solve the "Cheapest Flights Within K Stops" constraint pattern that Google directly tests.

Ready to quiz yourself?