ALGORITHMS Lecture Notes - Erik Demaine, Weight Function, Directed Acyclic Graph
Document Summary
Instructors: erik demaine, jason ku, and justin solomon. Strength of a relationship in a social network: two common ways to represent weights computationally: Inside graph representation: store edge weight with each vertex in adjacency lists. Store separate set data structure mapping each edge to its weight: we assume a representation that allows querying the weight of an edge in o(1) time. (s, t) = if no path from s to t. Weighted shortest paths algorithms: next four lectures: algorithms to nd shortest-path weights in weighted graphs, (no parent pointers: can reconstruct shortest paths tree in linear time after. Next page!: already know one algorithm: breadth-first search! Runs in o(|v | + |e|) time when, e. g. graph has positive weights, and all weights are the same. Shortest-paths tree: for bfs, we kept track of parent pointers during search. If p (v) not assigned and (s, v) = (s, u) + w(u, v):
