What is the complexity of the BFS algorithm for the shortest path on the unweighted grid?

The grid is a classical maze with a starting point and exit, need to find an exit. Can move only vertically and horizontally.

Found the answer here: https://stackoverflow.com/questions/50901203/dfs-and-bfs-time-and-space-complexities-of-number-of-islands-on-leetcode#:%7E:text=The%20way%20I%20see%20it,cols

  • $\begingroup$ What does unweighted grid mean? If each length is zero, all paths have length zero. If every "point on a rectangular grid" is connected to each of its axis-parallel neighbours by an edge of length 1, the length of every shortest path is the Manhattan distance - no search called for. (There is a mildly irritating typo in the title.) $\endgroup$ – greybeard Mar 11 at 8:31
  • $\begingroup$ It is like a classical maze, you have a starting point, need to find an exit. No weights, so we can use BFS, but what is complexity? BFS standard is O(V+E), but I saw some sources state that it is O(V) here, just don't understand why? $\endgroup$ – ogbofjnr Mar 11 at 8:35
  • 1
    $\begingroup$ Don't tell me: edit the question. $\endgroup$ – greybeard Mar 11 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.