Is BFS best search algorithm?

Question

I know about Dijkstra's agorithm, Floyd-Warshall algorithm and Bellman-Ford algorithm for finding the cheepest paths between 2 vertices in graphs.

But when all the edges have the same cost, the cheapest path is the path with minimal number of edges? Am I right? There is no reason to implement Dijkstra or Floyd-Warshall, the best algorithm is Breadth-First search from source, until we reach the target? In the worst case, you will have to traverse all the vertices, so the complexity is O(V)? There is no better solution? Am I right?

But there are tons of articles on the internet, which talk about shortest paths in grids with obstacles and they mention Dijkstra or A*. Even on StackOverfow - Algorithm to find the shortest path, with obstacles or here http://qiao.github.io/PathFinding.js/visual/

So, are all those people stupid? Or am I stupid? Why do they recommend so complicated things like Dijkstra to beginners, who just want to move their enemies to the main character in a regular grid? It is like when someone asks how to find the minimum number in a list, and you recommend him to implement heap sort and then take the first element from sorted array.

Answer 1

BFS (Breadth-first search) is just a way of travelling a graph. It's goal is to visit all the vertices. That's all. Another way of travelling the graph can be for example DFS.

Dijkstra is an algorithm, which goal is to find the shortest path from given vertex v to all other vertices.

Dijkstra is not so complicated, even for beginners. It travels the graph, using BFS + doing something more. This something more is storing and updating the information about the shortest path to the currently visited vertex.

If you want to find shortest path between 2 vertices v and q, you can do that with a little modification of Dijkstra. Just stop when you reach the vertex q.

The last algorithm - A* is somewhat the most clever (and probably the most difficult). It uses a heuristic, a magic fairy, which advises you where to go. If you have a good heuristic function, this algorithm outperforms BFS and Dijkstra. A* can be seen as an extension of Dijktra's algorithm (heuristic function is an extension).

But when all the edges have the same cost, the cheapest path is the path with minimal number of edges? Am I right?

Right.

There is no reason to implement Dijkstra or Floyd-Warshall, the best algorithm is Breadth-First search? Am I right?

When it comes to such a simple case where all edges have the same weight - you can use whatever method you like, everything will work. However, A* with good heuristic should be faster then BFS and Dijkstra. In the simulation you mentioned, you can observe that.

So, are all those people stupid? Or am I stupid? Why do they recommend so complicated things like Dijkstra to beginners, who just want to move their enemies to the main character in a regular grid?

They have a different problem, which changes the solution. Read the problem description very carefully:

(...) The catch being any point (excluding A and B) can have an obstacle obstructing the path, and thus must be detoured.

Enemies can have obstacles on the way to the main character. So, for example A* is a good choice in such case.

Answer 2

BFS is like a "brute-force" to find the shortest path in an unweighted graph. Dijkstra's is like a "brute-force" for weighted graphs. If you were to use Dijkstra's on an unweighted graph, it would be exactly equivalent to BFS.

So, Dijkstra's can be considered an extension of BFS. It is not really a "complicated" algorithm; it's only slightly more complex than BFS.

A* is an extension to Dijkstra's that uses a heuristic to speed up the pathfinding.