0
Challenge · 54Graphs
BFS and shortest path
Graphsused in ~95% of apps
The most useful graph algorithm you will learn, and you already wrote it in tier 6. On an unweighted graph, breadth first search does not merely find a route. It finds the shortest one, and it proves it.
Core idea. Breadth first search reaches nodes in order of distance, so the first time you arrive anywhere is by the shortest route and that distance is final. Nothing needs revisiting. This is only true when every edge costs the same, which is what unweighted means.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
breadth first, driven by a queue
the queue, oldest on the left
0
distance from 0
node 0: 0
put the start in the queue at distance 0
step 1 of 9
A queue takes the oldest first, so everything one step away is finished before anything two steps away.
↑ play a little first, then dig in