DSA Part 13: Shortest Paths & Topological Order

1. Problem and Motivation

Once a graph is built and you can traverse it with BFS or DFS, the next question is almost always about weight: which route costs the least, and in what order must dependent steps run? A mapping app needs the cheapest route between two points, not just any route. A build system needs to know which modules to compile before others so that nothing runs against code that hasn't been produced yet. Both problems live in the same graph, but neither is answered by traversal alone.

This lesson covers two algorithm families that answer those questions. Shortest path algorithms — Dijkstra's, Bellman-Ford, and Floyd-Warshall — find least-cost routes under different assumptions about edge weights and how many sources you need distances from. Topological sort — via Kahn's algorithm or a DFS-based approach — orders a directed acyclic graph so every dependency appears before what depends on it. Together they cover most weighted-routing and ordering problems that show up in interviews and in production systems such as routers, build tools, and package managers.

2. Prerequisites

This lesson assumes you can already represent a graph (adjacency list, matrix, or edge list) and traverse one. If BFS and DFS are not yet second nature, start with Part 12: Graph Traversal & Representations before continuing here — every algorithm below builds directly on those traversal patterns.

Dijkstra's algorithm also depends on a min-heap to always expand the closest unvisited vertex next. If the mechanics of pushing, popping, and re-heapifying a priority queue are unfamiliar, review the heap section of Part 11: Heaps, Sorting & Hashing first.

3. Shortest Path Algorithms

Dijkstra algorithm step-by-step showing priority queue processing and distance updates — Dijkstra's algorithm: greedily select the nearest unvisited vertex, update neighbor distances, and repeat until all vertices are processed

Shortest Path Algorithm Selection

flowchart TD
    A["Shortest Path Problem"] --> B{"Negative
Weights?"}
    B -->|No| C{"Single Source?"}
    B -->|Yes| D{"Negative
Cycles?"}

    C -->|Yes| E{"Weighted?"}
    C -->|No| F["Floyd-Warshall
O V cubed"]

    E -->|Yes| G["Dijkstra
O V+E log V"]
    E -->|No| H["BFS
O V+E"]

    D -->|No| I["Bellman-Ford
O VE"]
    D -->|Yes| J["No Solution
Detect and Report"]

    style G fill:#e8f4f4,stroke:#3B9797
    style H fill:#e8f4f4,stroke:#3B9797
    style I fill:#f0f4f8,stroke:#16476A
    style J fill:#fff5f5,stroke:#BF092F

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights. It works on a greedy principle: always process the unvisited vertex with the smallest known distance, then update its neighbors. This greedy choice is safe because non-negative weights guarantee that once a vertex is finalized (popped from the priority queue), no shorter path to it can exist.

Key Insight

Think of Dijkstra as a "wavefront" expanding outward from the source — it always expands to the nearest unvisited node first, like ripples on a pond. The priority queue (min-heap) efficiently selects which node to expand next. Time complexity: $O((V + E) \log V)$ with a binary heap.

Algorithm steps: (1) Initialize all distances to ∞ except source = 0. (2) Push source into a min-heap. (3) Pop the minimum-distance vertex, relax all its edges (if $dist[u] + weight(u,v) \lt dist[v]$, update $dist[v]$). (4) Repeat until the heap is empty. The relaxation step is the core — it asks "can we reach $v$ faster by going through $u$?"

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    """
    Dijkstra's Algorithm for shortest paths
    Time: O((V + E) log V), Space: O(V)
    Works for non-negative weights only
    """
    # Distance to all nodes (infinity initially)
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # Priority queue: (distance, node)
    pq = [(0, start)]

    # Track visited nodes
    visited = set()

    while pq:
        dist, node = heapq.heappop(pq)

        if node in visited:
            continue

        visited.add(node)

        for neighbor, weight in graph[node]:
            if neighbor not in visited:
                new_dist = dist + weight

                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(pq, (new_dist, neighbor))

    return distances

# Example: Weighted graph
graph = defaultdict(list)
edges = [
    (0, 1, 4), (0, 2, 1),
    (1, 3, 1),
    (2, 1, 2), (2, 3, 5),
    (3, 4, 3)
]

for u, v, w in edges:
    graph[u].append((v, w))

distances = dijkstra(graph, 0)
print("Shortest distances from 0:")
for node, dist in sorted(distances.items()):
    print(f"  To {node}: {dist}")

// Dijkstra's Algorithm - O((V + E) log V)
// Non-negative weights only
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>

class Dijkstra {
public:
    static std::unordered_map<int, int> shortestPaths(
            std::unordered_map<int, std::vector<std::pair<int, int>>>& graph, int start) {

        std::unordered_map<int, int> distances;
        for (auto& [node, _] : graph)
            distances[node] = std::numeric_limits<int>::max();
        distances[start] = 0;

        // Min heap: (distance, node)
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                           std::greater<>> pq;
        pq.push({0, start});

        std::unordered_set<int> visited;

        while (!pq.empty()) {
            auto [dist, node] = pq.top(); pq.pop();

            if (visited.count(node)) continue;
            visited.insert(node);

            for (auto& [neighbor, weight] : graph[node]) {
                int newDist = dist + weight;
                if (newDist < distances[neighbor]) {
                    distances[neighbor] = newDist;
                    pq.push({newDist, neighbor});
                }
            }
        }
        return distances;
    }
};

// Dijkstra's Algorithm - O((V + E) log V)
// Non-negative weights only
import java.util.*;

class Dijkstra {
    public static Map<Integer, Integer> shortestPaths(
            Map<Integer, List<int[]>> graph, int start) {

        Map<Integer, Integer> distances = new HashMap<>();
        for (int node : graph.keySet())
            distances.put(node, Integer.MAX_VALUE);
        distances.put(start, 0);

        // Min heap: {distance, node}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, start});

        Set<Integer> visited = new HashSet<>();

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int dist = curr[0], node = curr[1];

            if (visited.contains(node)) continue;
            visited.add(node);

            for (int[] edge : graph.getOrDefault(node, new ArrayList<>())) {
                int neighbor = edge[0], weight = edge[1];
                int newDist = dist + weight;
                if (newDist < distances.getOrDefault(neighbor, Integer.MAX_VALUE)) {
                    distances.put(neighbor, newDist);
                    pq.offer(new int[]{newDist, neighbor});
                }
            }
        }
        return distances;
    }
}

Bellman-Ford Algorithm

Bellman-Ford solves the single-source shortest path problem even when edges have negative weights — something Dijkstra cannot handle. The tradeoff is speed: $O(V \times E)$ versus Dijkstra's $O((V+E) \log V)$. Its key advantage is the ability to detect negative-weight cycles — loops where total weight is negative, making "shortest path" undefined (you could loop forever getting shorter).

How it works: Relax every edge in the graph $V-1$ times. After $k$ iterations, the algorithm guarantees correct shortest distances for all paths using at most $k$ edges. Since the longest simple path has at most $V-1$ edges, $V-1$ iterations suffice. If a $V$-th iteration still reduces a distance, a negative cycle exists.

When to Choose Bellman-Ford over Dijkstra

Use Bellman-Ford when: (1) edges can have negative weights (e.g., currency arbitrage, network routing with costs/rebates), (2) you need to detect negative cycles, or (3) the graph is given as an edge list (Bellman-Ford iterates over edges directly). For all other cases, prefer Dijkstra for speed.

def bellman_ford(vertices, edges, start):
    """
    Bellman-Ford Algorithm
    Time: O(V * E), Space: O(V)
    Handles negative weights, detects negative cycles
    """
    # Initialize distances
    distances = {v: float('inf') for v in vertices}
    distances[start] = 0

    # Relax edges V-1 times
    for _ in range(len(vertices) - 1):
        for u, v, weight in edges:
            if distances[u] != float('inf'):
                if distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight

    # Check for negative cycles
    for u, v, weight in edges:
        if distances[u] != float('inf'):
            if distances[u] + weight < distances[v]:
                return None  # Negative cycle detected

    return distances

# Example
vertices = [0, 1, 2, 3, 4]
edges = [
    (0, 1, 4), (0, 2, 1),
    (1, 3, 1),
    (2, 1, 2), (2, 3, 5),
    (3, 4, 3)
]

distances = bellman_ford(vertices, edges, 0)
print("Bellman-Ford distances from 0:")
for node, dist in sorted(distances.items()):
    print(f"  To {node}: {dist}")

// Bellman-Ford Algorithm - O(V * E)
// Handles negative weights, detects negative cycles
#include <vector>
#include <limits>
#include <unordered_map>

class BellmanFord {
public:
    static std::unordered_map<int, int> shortestPaths(
            std::vector<int>& vertices,
            std::vector<std::tuple<int, int, int>>& edges, int start) {

        std::unordered_map<int, int> distances;
        for (int v : vertices)
            distances[v] = std::numeric_limits<int>::max();
        distances[start] = 0;

        // Relax edges V-1 times
        for (int i = 0; i < vertices.size() - 1; i++) {
            for (auto& [u, v, weight] : edges) {
                if (distances[u] != std::numeric_limits<int>::max() &&
                    distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                }
            }
        }

        // Check for negative cycles
        for (auto& [u, v, weight] : edges) {
            if (distances[u] != std::numeric_limits<int>::max() &&
                distances[u] + weight < distances[v]) {
                return {};  // Negative cycle detected
            }
        }

        return distances;
    }
};

// Bellman-Ford Algorithm - O(V * E)
// Handles negative weights, detects negative cycles
import java.util.*;

class BellmanFord {
    public static Map<Integer, Integer> shortestPaths(
            int[] vertices, int[][] edges, int start) {

        Map<Integer, Integer> distances = new HashMap<>();
        for (int v : vertices)
            distances.put(v, Integer.MAX_VALUE);
        distances.put(start, 0);

        // Relax edges V-1 times
        for (int i = 0; i < vertices.length - 1; i++) {
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], weight = edge[2];
                if (distances.get(u) != Integer.MAX_VALUE &&
                    distances.get(u) + weight < distances.get(v)) {
                    distances.put(v, distances.get(u) + weight);
                }
            }
        }

        // Check for negative cycles
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            if (distances.get(u) != Integer.MAX_VALUE &&
                distances.get(u) + weight < distances.get(v)) {
                return null;  // Negative cycle detected
            }
        }

        return distances;
    }
}

Floyd-Warshall Algorithm

Floyd-Warshall solves the all-pairs shortest path problem: the shortest distance between every pair of vertices, not just from one source. Instead of running Dijkstra or Bellman-Ford from every vertex, it uses a single dynamic-programming pass over all possible intermediate vertices. It works with negative edge weights, but — like Bellman-Ford — assumes no negative cycle when reporting a real distance.

How it works: Initialize $dist[i][j]$ to the direct edge weight (or $0$ if $i=j$, $\infty$ if no edge exists). Then, for each vertex $k$ considered as an intermediate stop, check every pair $(i, j)$: if routing through $k$ is shorter — $dist[i][k] + dist[k][j] \lt dist[i][j]$ — update $dist[i][j]$. After looping $k$ over all vertices, every $dist[i][j]$ holds the true shortest distance using any subset of vertices as intermediates. This gives $O(V^3)$ time and $O(V^2)$ space from three nested loops, and a negative cycle reveals itself as a negative value on the diagonal ($dist[v][v] \lt 0$).

When to Choose Floyd-Warshall

Reach for Floyd-Warshall when you need distances between every pair of vertices, the graph is dense (edges close to $V^2$), or $V$ is small enough that $O(V^3)$ is cheap — and the triple-loop implementation is simpler to write correctly than looping Dijkstra over every source. On a sparse graph with many vertices, running Dijkstra from each source ($O(V(V+E)\log V)$) is usually faster; Floyd-Warshall wins on simplicity and dense, small-to-medium graphs.

def floyd_warshall(num_vertices, edges):
    """
    Floyd-Warshall Algorithm - All-Pairs Shortest Paths
    Time: O(V^3), Space: O(V^2)
    Handles negative weights, detects negative cycles
    """
    INF = float('inf')
    dist = [[INF] * num_vertices for _ in range(num_vertices)]
    for v in range(num_vertices):
        dist[v][v] = 0

    for u, v, weight in edges:
        dist[u][v] = min(dist[u][v], weight)

    for k in range(num_vertices):
        for i in range(num_vertices):
            if dist[i][k] == INF:
                continue
            for j in range(num_vertices):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    # Detect negative cycle: distance from a vertex to itself turns negative
    for v in range(num_vertices):
        if dist[v][v] < 0:
            return None  # Negative cycle detected

    return dist

# Example: 4 vertices, one negative edge, no negative cycle
num_vertices = 4
edges = [
    (0, 1, 5), (0, 2, 10),
    (1, 2, -3),
    (2, 3, 2),
    (3, 0, 1)
]

matrix = floyd_warshall(num_vertices, edges)
print("All-pairs shortest distances:")
for row in matrix:
    print(row)

// Floyd-Warshall Algorithm - All-Pairs Shortest Paths
// Time: O(V^3), Space: O(V^2)
#include <vector>
#include <tuple>
#include <limits>

class FloydWarshall {
public:
    static std::vector<std::vector<long long>> shortestPaths(
            int numVertices, std::vector<std::tuple<int, int, int>>& edges) {

        const long long INF = std::numeric_limits<long long>::max() / 2;
        std::vector<std::vector<long long>> dist(
            numVertices, std::vector<long long>(numVertices, INF));

        for (int v = 0; v < numVertices; v++) {
            dist[v][v] = 0;
        }

        for (auto& [u, v, weight] : edges) {
            if (weight < dist[u][v]) {
                dist[u][v] = weight;
            }
        }

        for (int k = 0; k < numVertices; k++) {
            for (int i = 0; i < numVertices; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < numVertices; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // Detect negative cycle: distance from a vertex to itself is negative
        for (int v = 0; v < numVertices; v++) {
            if (dist[v][v] < 0) {
                return {};  // Negative cycle detected
            }
        }

        return dist;
    }
};

// Floyd-Warshall Algorithm - All-Pairs Shortest Paths
// Time: O(V^3), Space: O(V^2)
import java.util.*;

class FloydWarshall {
    public static long[][] shortestPaths(int numVertices, int[][] edges) {
        final long INF = Long.MAX_VALUE / 2;
        long[][] dist = new long[numVertices][numVertices];

        for (long[] row : dist) Arrays.fill(row, INF);
        for (int v = 0; v < numVertices; v++) dist[v][v] = 0;

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            if (weight < dist[u][v]) dist[u][v] = weight;
        }

        for (int k = 0; k < numVertices; k++) {
            for (int i = 0; i < numVertices; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < numVertices; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // Detect negative cycle: distance from a vertex to itself is negative
        for (int v = 0; v < numVertices; v++) {
            if (dist[v][v] < 0) return null;  // Negative cycle detected
        }

        return dist;
    }
}

Two related shortest-path-family topics — Minimum Spanning Tree (Kruskal's and Prim's algorithms) and A* search — are not covered here; they are a gap in this lesson's roadmap, not a promise of a future lesson.

4. Topological Sort

A topological ordering of a Directed Acyclic Graph (DAG) arranges vertices so that for every directed edge $u \to v$, vertex $u$ appears before $v$. Think of it as a valid execution order — like determining which courses to take first given prerequisites, or which build targets to compile before others.

Two classic approaches exist: Kahn's Algorithm (BFS-based) repeatedly removes vertices with zero in-degree, while the DFS-based approach adds vertices to the result in reverse post-order. Both run in $O(V + E)$. A topological sort exists if and only if the graph has no cycles — if Kahn's algorithm processes fewer than $V$ vertices, a cycle exists.

Real-World Applications

Build systems (Makefile dependencies), package managers (npm/pip install order), spreadsheet cell evaluation (formulas depend on other cells), course scheduling (prerequisites), and task pipelines (CI/CD stages). Any problem with "do X before Y" constraints maps to topological sort.

from collections import deque, defaultdict

def topological_sort_kahn(num_nodes, edges):
    """
    Kahn's Algorithm (BFS-based)
    Time: O(V + E), Space: O(V)
    Returns topological order or empty list if cycle exists
    """
    # Build graph and compute in-degrees
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    # Start with nodes having no prerequisites
    queue = deque([i for i in range(num_nodes) if in_degree[i] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # Check if all nodes are included (no cycle)
    return result if len(result) == num_nodes else []

def topological_sort_dfs(num_nodes, edges):
    """
    DFS-based topological sort
    Time: O(V + E), Space: O(V)
    """
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = [0] * num_nodes  # 0: unvisited, 1: visiting, 2: visited
    result = []

    def dfs(node):
        if visited[node] == 1:  # Cycle detected
            return False
        if visited[node] == 2:
            return True

        visited[node] = 1  # Mark as visiting

        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False

        visited[node] = 2  # Mark as visited
        result.append(node)
        return True

    for i in range(num_nodes):
        if visited[i] == 0:
            if not dfs(i):
                return []  # Cycle detected

    return result[::-1]  # Reverse for topological order

# Example: Course Schedule
# 0 -> 1 -> 3
#      |
# 2 ---+
num_courses = 4
prerequisites = [(0, 1), (1, 3), (2, 1)]

print("Topological order (Kahn):", topological_sort_kahn(num_courses, prerequisites))
print("Topological order (DFS):", topological_sort_dfs(num_courses, prerequisites))

// Topological Sort - Kahn's Algorithm (BFS)
// Time: O(V + E), Space: O(V)
#include <vector>
#include <queue>
#include <unordered_map>

class TopologicalSort {
public:
    // Kahn's Algorithm (BFS)
    static std::vector<int> kahnSort(int numNodes, std::vector<std::pair<int, int>>& edges) {
        std::unordered_map<int, std::vector<int>> graph;
        std::vector<int> inDegree(numNodes, 0);

        for (auto& [u, v] : edges) {
            graph[u].push_back(v);
            inDegree[v]++;
        }

        std::queue<int> q;
        for (int i = 0; i < numNodes; i++)
            if (inDegree[i] == 0) q.push(i);

        std::vector<int> result;
        while (!q.empty()) {
            int node = q.front(); q.pop();
            result.push_back(node);

            for (int neighbor : graph[node]) {
                if (--inDegree[neighbor] == 0)
                    q.push(neighbor);
            }
        }

        return (result.size() == numNodes) ? result : std::vector<int>();
    }

    // DFS-based topological sort
    static std::vector<int> dfsSort(int numNodes, std::vector<std::pair<int, int>>& edges) {
        std::unordered_map<int, std::vector<int>> graph;
        for (auto& [u, v] : edges)
            graph[u].push_back(v);

        std::vector<int> visited(numNodes, 0);  // 0=unvisited, 1=visiting, 2=visited
        std::vector<int> result;

        std::function<bool(int)> dfs = [&](int node) {
            if (visited[node] == 1) return false;  // Cycle
            if (visited[node] == 2) return true;

            visited[node] = 1;
            for (int neighbor : graph[node])
                if (!dfs(neighbor)) return false;

            visited[node] = 2;
            result.push_back(node);
            return true;
        };

        for (int i = 0; i < numNodes; i++)
            if (visited[i] == 0 && !dfs(i)) return {};

        std::reverse(result.begin(), result.end());
        return result;
    }
};

// Topological Sort - Kahn's Algorithm (BFS) and DFS
import java.util.*;

class TopologicalSort {
    // Kahn's Algorithm (BFS)
    public static List<Integer> kahnSort(int numNodes, int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[numNodes];

        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            inDegree[edge[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numNodes; i++)
            if (inDegree[i] == 0) queue.offer(i);

        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);

            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (--inDegree[neighbor] == 0)
                    queue.offer(neighbor);
            }
        }

        return (result.size() == numNodes) ? result : new ArrayList<>();
    }

    // DFS-based topological sort
    public static List<Integer> dfsSort(int numNodes, int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges)
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);

        int[] visited = new int[numNodes];  // 0=unvisited, 1=visiting, 2=visited
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < numNodes; i++)
            if (visited[i] == 0 && !dfs(graph, i, visited, result))
                return new ArrayList<>();

        Collections.reverse(result);
        return result;
    }

    private static boolean dfs(Map<Integer, List<Integer>> graph, int node,
                               int[] visited, List<Integer> result) {
        if (visited[node] == 1) return false;  // Cycle
        if (visited[node] == 2) return true;

        visited[node] = 1;
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>()))
            if (!dfs(graph, neighbor, visited, result)) return false;

        visited[node] = 2;
        result.add(node);
        return true;
    }
}

5. Exercises and Mastery

Easy

Network Delay Time (LeetCode 743): given directed weighted edges, a source node, and a signal that must reach every one of $n$ nodes, find the minimum time for that to happen using Dijkstra's algorithm; return $-1$ if some node is unreachable.

Medium

Course Schedule II (LeetCode 210): given course prerequisites, return a valid order to take all courses using topological sort (Kahn's or DFS-based); return an empty array if a cycle makes no ordering possible.

Hard

Cheapest Flights Within K Stops (LeetCode 787): find the cheapest price from a source to a destination using at most $k$ intermediate stops. Plain Dijkstra doesn't respect the stop limit safely, so solve it with Bellman-Ford-style relaxation capped at $k+1$ rounds — each round relaxes every edge once, corresponding to one additional stop.

Mastery challenge: A logistics platform must route deliveries across a road network where a handful of roads carry a rebate (a negative edge weight) for subsidized regions, and must also validate a daily task-dependency graph for its warehouse robots before execution begins. Choose the correct shortest-path algorithm for the road network and justify why Dijkstra becomes unsafe the moment one negative edge exists. Choose Kahn's or the DFS-based approach for the task graph, and explain what must happen operationally if a negative cycle or a dependency cycle is detected instead of a clean answer.

Review rhythm: tomorrow, redo Dijkstra and Kahn's algorithm from memory without notes; next week, implement Bellman-Ford and Floyd-Warshall in a language you have not used yet; several weeks later, solve Cheapest Flights Within K Stops cold and explain why plain Dijkstra fails on it. Finally, teach the difference between single-source and all-pairs shortest paths, and between BFS-based and DFS-based topological sort, to someone who only knows basic graph traversal.

6. Summary Cheat Sheet

BFS finds shortest paths only in unweighted graphs — every edge costs the same, so level-order distance is minimum distance.
Dijkstra's algorithm finds single-source shortest paths in $O((V+E)\log V)$ when every edge weight is non-negative; it silently produces wrong answers if any edge is negative.
Bellman-Ford solves single-source shortest paths in $O(V \times E)$ even with negative edges, and doubles as a negative-cycle detector via a $V$-th relaxation pass.
Floyd-Warshall computes all-pairs shortest paths in $O(V^3)$ time and $O(V^2)$ space — the simplest choice for dense graphs or small $V$ when every pair's distance is needed, though slower than running Dijkstra from every vertex on a large sparse graph.
Quick decision list: unweighted → BFS; weighted, non-negative, single source → Dijkstra; negative weights or cycle detection → Bellman-Ford; all-pairs on a small or dense graph → Floyd-Warshall.
Topological sort exists only for DAGs; Kahn's algorithm (BFS on in-degrees) and the DFS-based approach (reverse post-order) both run in $O(V+E)$ and both detect cycles when they cannot order every vertex.
Minimum Spanning Tree (Kruskal's/Prim's) and A* search are related but distinct shortest-path-family topics not covered in this lesson.