CS431 Chapter 4: Analyzing Graphs
17 Apr 2019
School
Department
Course
Professor
Document Summary
Store both edges make sure your algorithm de-dups. Store one edge (x,y) such that x < y makes sure your algo handles asymmetry. Adjacency lists to edge lists flatmap adjacency lists to emit tuples. In other words, the rich get richer, the poor get poorer. Find the shortest path from a source node to one or more target node (lowest weight or cost) Go larger and larger and visit every node. Initialization: for all nodes except for start node, d = inf. For all m belong to adjacent list: emit(m, d+1), also emit the distance to self. Selects minimum distance path for each reachable node. Additional bookkeeping needed to keep track of actual path. Each mapreduce iteration advances the "frontier" by one hop. Subsequent iterations include more reachable nodes as frontier expands. Multiple iterations are needed to explore entre graph. Have to emit (n, adjacency list) as well. At each step, only pursues edges from min-cost path inside frontier.
