Can anyone explain to me why the BFS algorithm finds the shortest distance from u to v ? i understand but i am unable toexplain it, i think i don't understand it enough.. :( ( my writing is bad sorry)
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3856 |
| 2 | jiangly | 3747 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3591 |
| 6 | gamegame | 3477 |
| 7 | Benq | 3468 |
| 8 | Radewoosh | 3462 |
| 9 | ecnerwala | 3451 |
| 10 | heuristica | 3431 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 168 |
| 2 | -is-this-fft- | 164 |
| 3 | Dominater069 | 160 |
| 4 | Um_nik | 159 |
| 5 | atcoder_official | 158 |
| 6 | djm03178 | 154 |
| 7 | adamant | 153 |
| 8 | awoo | 148 |
| 8 | luogu_official | 148 |
| 10 | TheScrasse | 146 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Feb/12/2025 14:03:01 (l2).
Desktop version, switch to mobile version.
Supported by
Since the way BFS works is by going through levels (first the closest are visited (directly adjacent), then the second closest (neighbours of adjacent)), thats why BFS will always find the best distance. the distance of v will always be the level it is at from the starting vertex.
in general bfs finds the shortest distance from one node to all other nodes when all edge weights are one. first you put all the children (v) of that node (source node) in the queue and set them visited and make their distance +1 with the parent. the process continues until all the nodes get visited. as you are putting all the children of that node and setting their distance as final so obviously their distance is the shortest from the source node because every time you are taking the shortest path from the source node to that node throught its children that is your are visiting the nodes by levels and all the nodes on the same level will be visited all together.