Jaewoo Song
Jaewoo Song

Categories

  • Tech

Today I solved a problem which should be approached with BFS.


https://www.acmicpc.net/problem/14217


This is about the shortest path-finding and can be easily solved with BFS.

But I started to think about why BFS should be used, not DFS.

Actually, I have used DFS well if I have to search through a graph.


I became to learn that DFS does not guarantee the shortest path.


For example, let’s assume a graph like this.

An example of DFS implementation for finding the shortest path.


If we are going to find a path from $1$ to $4$, the answer would be $1$->$4$ and the sum is $1$.

But if we use DFS, then the algorithm goes as deep as possible, so it might determine $1$->$2$->$4$ or $1$->$2$->$3$->$4$ as the shortest path.

Of course, we can save all cases and returns the shortest one as the answer but this is ineffective temporally and spatially.


On the other hand, with BFS after checking all children and finding the destination, the algorithm returns the length.

So it can recognize $1$->$4$ as the required answer.