Looking for some tutorials / references that discuss Breadth First Search that takes into consideration the cost of paths, but could not find much information.

Could someone refer a tutorial?

  • 3
    $\begingroup$ What exactly are you looking for? Breadth-first search as used to find shortest paths is probably contained in every textbook on the subject. $\endgroup$ – Raphael Nov 6 '12 at 14:29
  • $\begingroup$ Are the edges in the graph weighted or un weighted? What do you mean by "take into consideration the cost of paths"? $\endgroup$ – Joe Nov 6 '12 at 21:06
  • $\begingroup$ It is called Uniform Cost Search (example with animation) and basically the cost is for edges , not paths $\endgroup$ – Anton Nov 7 '12 at 10:17

From a general point of view: there are tons, but I do sincerely recommend you the latest volume on Heuristic Search: Heuristic Search: Theory and Applications by Stefan Edelkamp and Stefan Schroedl.

From a specific point of view: in spite of the graph being directed or not, breadth-first search taking costs into account

  1. If no heuristics are available, then it amounts to either Dijkstra or Uniform Cost Search. An excellent discussion between these two algorithms is presented in Felner, Ariel, "Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm", Symposium on Combinatorial Search, Barcelona (Spain), 2011.
  2. If heuristics are available Then there are also a number of interesting alternatives: A$^*$ is the usual one but RBFS also expands the same nodes in the same order with a linear consumption of memory. For these, I do strongly recommend the book by Stefan Edelkamp and Stefan Schroedl.

Hope this helps,


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.