ALGORITHMS Lecture Notes - Erik Demaine, Sign (Mathematics), Fibonacci Heap
Document Summary
Instructors: erik demaine, jason ku, and justin solomon. Grow a sphere centered at source s. Repeatedly explore closer vertices before further ones. But how to explore closer vertices if you don"t know distances beforehand: observation 1: if weights non-negative, monotonic distance increase along shortest paths. I. e. , if vertex u appears on a shortest path from s to v, then (s, u) (s, v) Let vx v be the subset of vertices reachable within distance x from s. If v vx, then any shortest path from s to v only contains vertices from vx. Perhaps grow vx one vertex at a time! (but growing for every x is slow if weights large: observation 2: can solve sssp fast if given order of vertices in increasing distance from s. Remove edges that go against this order (since cannot participate in shortest paths) May still have cycles if zero-weight edges: repeatedly collapse into single vertices.
