Class Notes (811,155)
Canada (494,530)
CMPT 225 (60)
John Edgar (28)

CMPT 225 Week 11 Lecture 2

2 Pages
Unlock Document

Simon Fraser University
Computing Science
CMPT 225
John Edgar

Possible to write Depth and Breadth first search with identical code, just different data structures. Shortest Path Problem What is smallest cost path from one vertex to another? Unweighted - shortest = least # of edges Weighted - shortest = smallest sum of edge weights (Edgser) Dijkstra's finds shortest path between one vertex and all other vertices Unweighted, want shortest path - just do breadth first search, stop when arrive at vertex A* is Dijkstra's with some changes, granddaddy pathfinding algorithm Dijkstra's Performs modified BFS that accounts for edge weights; uses priority queue instead of a queue Node with least cost is removed first Queue records the total cost to reach each node from the start node Cost in the piority queue updated when necessary (when find shortest/better queue) - but, pq doesn't do this by default -> this is the ugly part Shortest path can be found by backtracking from that node's entry in results list Algorithms didn't distinguish between permanent blocks vs temporary blocks (Age of Empires, Baldur's Gate) 3 processes: Initialization: Insert record for each vertex into pq, re
More Less

Related notes for CMPT 225

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.