COMPSCI 61B Lecture Notes - Lecture 29: Topological Sorting, Call Stack, Binary Heap
28 Aug 2017
School
Department
Course
Professor
Document Summary
Dfs is worse when there"s a deep call stack (spindly graph) Bfs is worse when the graph is bushy. Goal: find the shortest paths from source vertex s to target vertex t. Observation: solution will always be a path with no cycles (assuming non-negative weights) 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. V - 1 edges (every vertex needs an. Bfs, adding edge to spt if not already in spt. Dfs, adding edge to spt if that edge yields better distance (edge relaxation) Visit vertices in order of best-known distance (best rst search) from source, relaxing each edge from the visited vertex (relax an edge: add to spt if better distance) Insert all vertices into fringe pq, storing vertices in order of distance from source. Repeat: remove closest vertex v from pq and relax all edges pointing from v.
