CS 106B Lecture Notes - Lecture 27: Priority Queue, Admissible Heuristic

• School: Stanford University
• Department: Computer Science
• Course: CS 106B
• Professor: Chris Piech, Chris Gregg

Document Summary

We look at paths of increasing length from the start: the only difference for djikstra"s algorithm is that the todo list is a. Don"t check goal when making all the next paths (just enqueue. Path from start node to itself is 0 (that is weight of first node) Skipping nodes that we have seen before: common mistakes edges it) How google maps work: make a todo list of paths, put a path with just the start in the todo list, while the todo list isn"t empty. Take a (cid:498)currpath(cid:499) out of the todo list. Call the last node in the currpath (cid:498)currnode(cid:499) If (cid:498)currnode(cid:499) is the goal, you are done. If you have seen currnode before, skip it. Make a newpath which is currpath + neighbor. In breadthfirst search the todo list is a queue: will find shortest path guaranteed, unless there are weights on the. Cuts down significantly on runtime and paths needed to.