Best BFS Search Algorithm?

Question

I know about Dijkstra's agorism, the Floyd-Warsall algorithm, and the Bellman-Ford algorithm for finding the simplest paths between two vertices in graphs.

But when all the ribs have the same value, is the cheapest way the way with the minimum number of edges? I'm right? There is no reason to implement Dijkstra or Floyd-Warshall, is the best algorithm to search for Breadth-First from the source until we reach the goal? In the worst case, you have to cross all the vertices, so the complexity is O (V)? No better solution? I'm right?

But there are many articles on the Internet that talk about the shortest paths in obstacle grids, and they mention Dijkstra or A *. Even in StackOverfow - Algorithm for finding the shortest path with obstacles or here http://qiao.imtqy.com/PathFinding.js/visual/

So, are all these people stupid? Or am I stupid? Why do they recommend for beginners such complicated things as Dijkstra who simply want to transfer their enemies to the main character in a regular grid? This is similar to when someone asks how to find the minimum number in the list, and you recommend that he implement heap sorting and then take the first element from the sorted array.

Answer 1

BFS (width search) is just a way to move a graph. The goal is to visit all the peaks. All this. Another way to move the graph may be, for example, DFS.

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

Dijkstra is not so complicated, even for beginners. He moves the chart using BFS + while doing something else. This is more than storing and updating information on the shortest path to the current peak visited.

If you want to find the shortest path between the two vertices v and q, you can do this with a small modification of Dijkstra. Just stop when you reach the top of q.

The last algorithm - A * is somewhat the smartest (and probably the most complex). He uses heuristics, a magic fairy who advises you where to go. If you have a good heuristic function, this algorithm is superior to BFS and Dijkstra. A * can be considered as an extension of the Dijktra algorithm (a heuristic function is an extension).

But when all faces have the same value, is the cheapest way the way with the minimum number of edges? I'm right?

Right

There is no reason to implement Dijkstra or Floyd-Warshall, the best algorithm is a search using the Breadth-First method? I'm right?

When it comes to such a simple case, when all the ribs have the same weight - you can use any method that you like, everything will work. However, A * with good heuristics should be faster than BFS and Dijkstra. In the simulation you mentioned, you can notice it.

So, are all these people stupid? Or am I stupid? Why do they recommend for beginners such complicated things as Dijkstra who simply want to transfer their enemies to the main character in a regular grid?

They have another problem that is changing the solution. Read the problem description carefully:

(...) The trick to any point (excluding A and B) can be an obstacle that impedes the path, and therefore should be disabled.

Enemies may have obstacles to the main character. So, for example, A * is a good choice in this case.

Answer 2

BFS is like brute force to find the shortest path in an unweighted chart. Dijkstra is like brute force for weighted charts. If you used Dijkstra on an unweighted chart, it would be exactly equivalent to BFS.

So, Dijkstra can be considered an extension of BFS. This is not quite a “complicated” algorithm; it is only a little more complicated than BFS.

A * is an extension for Dijkstra that uses heuristic to speed up the search for a path.

Answer 3

But when all the edges have the same value, the cheapest way is the way with the minimum number of edges. Yes

If you really understood the message you linked, you would notice that the problem they want to solve is different from yours.