Lab: graph algorithms
Three guided graph exercises — network delay time with Dijkstra's, course schedule ordering with Kahn's, and cycle detection for prerequisites.
- Solve network delay time using Dijkstra's algorithm
- Return a valid course order using Kahn's topological sort
- Detect a prerequisite cycle using DFS 3-colour marking
These three problems are the standard applications of the algorithms from the previous lessons. Each one restates a familiar algorithm in a new setting. Work through the "think first" prompt, then check your implementation.
Problem 1: network delay time
Problem. You are given a list of directed, weighted edges times where
times[i] = [u, v, w] (source, destination, travel time). There are n nodes
numbered 1 to n, and a starting node k. Return the minimum time for all
nodes to receive a signal from k, or -1 if any node is unreachable.
network_delay_time([[2,1,1],[2,3,1],[3,4,1]], n=4, k=2) → 2.
Think first. Run Dijkstra from node k. Once you have the shortest
distances to all nodes, the answer is the maximum distance (the last node to
receive the signal). If any distance is still infinity, return -1.
Implement network_delay_time(times, n, k). Run Dijkstra from k, return the max shortest distance to any node, or -1 if any node is unreachable.
network_delay_time([[2,1,1],[2,3,1],[3,4,1]], 4, 2) → 2Problem 2: course schedule order
Problem. There are n courses numbered 0 to n-1. Given a list of
prerequisites pairs [a, b] meaning "take b before a", return a valid
order to take all courses, or an empty list if no valid order exists.
course_schedule_order(4, [[1,0],[2,0],[3,1],[3,2]]) → [0, 1, 2, 3]
(or any other valid topological order).
Think first. Build a directed graph where b → a for each [a, b].
Run Kahn's algorithm. If the output contains all n courses, return it.
Otherwise a cycle exists — return [].
Implement course_schedule_order(n, prerequisites) using Kahn's algorithm. Return a valid ordering or [] if a cycle is detected.
course_schedule_order(4, [[1,0],[2,0],[3,1],[3,2]]) → [0, 1, 2, 3]course_schedule_order(2, [[1,0],[0,1]]) → []Problem 3: can you finish all courses?
Problem. Same setup as above, but just return True if all courses can be
finished (no cycle) and False if a cycle makes it impossible.
can_finish_all_courses(2, [[1,0],[0,1]]) → False.
Think first. Use DFS 3-colour marking. A grey node encountered during DFS
means there is a cycle. Alternatively, reuse Kahn's: a cycle exists whenever
the output is shorter than n.
Implement can_finish_all_courses(n, prerequisites) returning True if no cycle exists. Use DFS 3-colour marking: WHITE=0, GREY=1, BLACK=2.
can_finish_all_courses(2, [[1,0],[0,1]]) → Falsecan_finish_all_courses(4, [[1,0],[2,0],[3,1],[3,2]]) → TrueWhere to go next
Next: the String Algorithms module — sliding window, two-pointer, and hashing techniques that solve string problems efficiently without nested loops.