COMPSCI 61B Lecture Notes - Lecture 23: Call Stack, Ptah, Consistent Heuristic
Document Summary
Correctness - do both work for all graphs. Bfs gives paths but also your paths are guaranteed to be shortest. Should be very similar as both consider all edges twice. Bfs is worse for absurdly bushy graphs. In our implementations, we have to spend (v) memory anyway to track distto and edgeto arrays. Can optimize by storing them in a map instead of an array. Neither of them are better - bfs gives shorter path. Bfs would not be a good choice for google maps as it returns path with shortest number of edges. Goal: find the shortest paths from source vertex s to some target vertex t. Observation: solution will always be a path with no cycles. Goal: find the shortest paths from source vertex s to every other vertex. Can think of as the union of the shortest paths to all vertices.
