📘 Keep shortest path from meaning fewer stops

What you’ll learn

1. What a Graph Is and How We Represent ItDefine a graph as vertices plus edges, and choose an adjacency list or matrix from how large m is next to n².A graph is a finite set of vertices and a set of edges relating them. Degree sums to 2m on an undirected graph because every edge has two ends. The adjacency matrix is an n-by-n table with O(1) edge queries and Θ(n²) space; the adjacency list is Θ(n + m) and scans a vertex in time proportional to its degree. Road networks, the web, and social graphs are typically sparse enough that the list is the default for traversal and shortest paths.
2. Traversal: Breadth-First and Depth-First SearchTrace BFS and DFS, explain why BFS finds fewest-edge paths, and give the O(n + m) list bound.BFS uses a FIFO queue and dequeues layer k before layer k+1, so the first discovery of v is a shortest hop-path from s on an unweighted graph. DFS uses a stack, dives, and backtracks; its finish times give a topological order on a DAG. Both run in O(n + m) on an adjacency list and Θ(n²) on a matrix. Choose by the property you need, not by speed.
3. Weighted Shortest Paths: Dijkstra's AlgorithmExplain how Dijkstra finds single-source shortest paths on non-negative weights by settling the closest unsettled vertex.BFS is not enough once edges have different costs. Dijkstra maintains tentative distances, settles the closest unsettled vertex, and relaxes its outgoing edges. Correctness needs every weight ≥ 0. The 1959 paper builds paths from P in increasing length and can stop at Q; the textbook run continues for every reachable vertex. A binary heap makes the algorithm O((n + m) log n). Negative weights belong to Bellman–Ford; all-pairs is a different problem.
4. Build a Mini Artifact: Model and Solve a Problem with GraphsModel a small real scenario as a graph, match an algorithm to the question, and defend the design.You write what a vertex is and what an edge is, choose directed and weighted explicitly, let the question pick BFS, Dijkstra, or a DFS topological sort, then trace the run by hand and check the invariants. A peer-style critique asks whether the model matches the world, not just whether the arithmetic adds up.

Grounded in trusted sources

• A Note on Two Problems in Connexion with Graphs — Numerische Mathematik 1 (1959), 269–271 (E. W. Dijkstra) — CWI scan
• EWD841a — later note on the 1959 paper and the 1956 ARMAC demo — Edsger W. Dijkstra archive, University of Texas at Austin — Harlingen–Maastricht, one minute
• 6.006 Lecture 13 — Graphs, adjacency lists, BFS — MIT 6.006 Fall 2011 (Demaine / Devadas) — G = (V, E), Θ(V + E), hop-distance levels
• 6.006 Lecture 16 — Shortest Paths II: Dijkstra — MIT OpenCourseWare, 6.006 Fall 2011 — w ≥ 0, binary-heap Θ((V + E) log V)
• 4.1 Undirected Graphs — Sedgewick and Wayne, Algorithms, 4th edition — degree, BFS hop-shortest paths, V + E
• 4.4 Shortest Paths — Sedgewick and Wayne, Algorithms, 4th edition — relaxation, Dijkstra, Bellman–Ford, Floyd–Warshall
• MIT 6.006 Fall 2011, Lecture 13 — G = (V, E), adjacency lists, space Θ(V + E).
• Sedgewick and Wayne, Algorithms, 4th edition, §4.1 — degree, adjacency-lists representation.

Every Wunder lesson is built from real, reputable sources — never invented.

Related courses