05 - Graphs

#cs451

Parallel BFS §

Simple Case - Unweighted Graph

Min distance from source to all other nodes

• dist(s) = 0
• dist(v) = 1 if there is an edge from s to v
• dist(v) = $1+mi{n}_u(dist(u))$ for all u s.t. there is an edge from u to v.