Please verify that the error is present in the most recent revision before reporting. verified
Chapter number or note title: [5. Basic Graph Algorithms]
Page number: [200]
Error description: [typo]
on the Proof of Lemma 5.1
The prefix path s->路路路->u is shorter than the shortest path from s to u
Suggested fix (if any):from s to u should be from s to v
This is the correctness proof of reachability, it is the basic proof of graph search algorithms. However, I got stuck on this when first time read the proof. First it's the typo of s to ~u~ v, second is the induction on the shortest-path distance. This is equivalent to the course video.
(I really like the idea of the WhateverFirstSearch framework and the data structure bag 馃槈, unlike most textbooks start with BFS and DFS.)
Please verify that the error is present in the most recent revision before reporting. verified
Chapter number or note title: [5. Basic Graph Algorithms]
Page number: [200]
Error description: [typo] on the Proof of Lemma 5.1 The prefix path s->路路路->u is shorter than the shortest path from s to u
Suggested fix (if any): from s to u should be from s to v
This is the correctness proof of reachability, it is the basic proof of graph search algorithms. However, I got stuck on this when first time read the proof. First it's the typo of s to ~u~ v, second is the induction on the shortest-path distance. This is equivalent to the course video.
(I really like the idea of the WhateverFirstSearch framework and the data structure bag 馃槈, unlike most textbooks start with BFS and DFS.)