Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 0 down vote favorite

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?

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

1 Answer

up vote 2 down vote accepted

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,

share|improve this answer
Thank you for the replies. – Roberta Rocha Nov 12 '12 at 11:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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