1

I need to help to validate whether my understanding of when to use Dijkstra and when BFS are correct.

My way of understanding BFS and Dijkstra, when to use what, am I correct?

As I see it. Being given a graph, that can be imagined as N-ary tree, where edges have no special value (all are same length) and we just want to get from node A to node B.

  1. To solve this, a BFS can be used
  2. Dijkstra can be used as well, but it is wasting memory, space and OP

However, being given a graph, where edges do have different values:

Lets imagine three nodes: A, B, C. Length from A to B is 1 Length from A to B is 5 Length from A to C is 100 Length from B to C is 1

So, yes, you can have more paths from node A to B. We are interested in shortest path from A to C.

There is NO way to solve this using plain BFS, am I correct...? I have to use Dijkstra...

From the implementation side, can Dijskstra be understood like BFS, but with a difference that we are having a container WHITE from wich we take always node with shortest tmp path... (priority queue) ? Whereas in plain BFS we can for WHITE use a queue or deque..? So Dijsktra's only difference is the priority queue...(and maybe some small things in algo, I wrote both BFS and Dijkstra, can not recall from head)

About complexities, on wiki I just am not sure with it. For BFS it should be O(a) + O(b)

  • a = Number of nodes
  • b = number of edges

But is there also the backtrack...? On wiki is just what is shown up...so it is oncomplete...? backtracking is also part of algorithm...vital one..I can backtrack at n * log(n), n being number of elements that I saved during traversal...

For Dijkstra....O(a * a) + O(b * b)...? Because I can visit some twice...? plus O(a) for setting each node's distances, plus O(n * long(n) ) for backtrack...?

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
Jan Glaser
  • 113
  • 3

1 Answers1

1

You have it mostly correct, but:

  • Note that Dijkstra's algorithm is just a special case of breadth-first search that priorities nodes based on a calculated cost rather than based on the order in which they can be reached.
  • The only extra cost involved in Dijkstra's algorithm, therefore, is the cost of maintaining the priority queue for determining which node to try first.
  • The complexity of Dijkstra's algorithm depends heavily, therefore, on what data structure you use to store that queue. There is a good pair of articles about A* search (http://www.redblobgames.com/pathfinding/a-star/introduction.html and http://www.redblobgames.com/pathfinding/a-star/implementation.html) that discuss the various data structures you can use. Note that A* search is very similar to Dijsktra's algorithm (it just uses a slightly different method to determine the priority for which node to examine first) and therefore the concepts discussed for A* also apply to implementations of Dijsktra's algorithm.
  • The similarity of A* and the fact that it can perform much better than Dijkstra's algorithm for many purposes means you may want to consider using it instead.
  • Neither breadth-first search nor Dijsktra's algorithm should involve backtracking, although the latter may involve rediscovering a node using a lower-cost path to reach it (which isn't really the same thing) if you have edges with negative cost (or, in A*, if your heuristic overestimates actual costs).
Jules
  • 17,614
  • 2
  • 33
  • 63