TuongOnArrival1's blog

By TuongOnArrival1, history, 6 hours ago, In English

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)

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 hours ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
3 hours ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

If we wish to find the shortest path from U to V in a tree:

We start BFS at U, effectively "hanging" the tree by U (in a tree you can re-designate any vertex as root).

By the nature of BFS, we first consider all verices that are adjacent to U (one edge away), then the ones that are adjacent to them (two edges away) and so on. In other words, traverse the tree "level by level".

We consider all vertices on a level before moving on to the next one. We also don't consider the same vertex twice.

Because of this, when we encounter a given vertex V on a level X, X must be the shortest distance to it. If it weren't, we would've encountered it earlier.

Keep in mind that this only works when the edges are not weighted (or all have the same weight).