Graph Theory37 sections · 1633 units
Open in Course

Intro

Why BFS is not enough for weighted graphs

Recall that BFS finds the shortest path by expanding in layers. Layer 11 (11 step away), then Layer 22 (22 steps away), etc. This assumes that "11 step" always equals "distance 11".

But look at this graph: ABA→B (Distance 1010) ACA→C (Distance 11) CBC→B (Distance 11) BFS will see ABA→B immediately (11 step) and declare the distance is 1010.

But the path ACBA→C→B is distance 1+1=21+1=2. BFS fails here. You need something smarter.

1769907042182-207l6kwnncr.jpg