Breadth First Search with cost

Question

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?

Answer 1

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,