CMPT 225 Lecture Notes - Priority Queue, Hash Table, Backtracking
4 Sep 2013
School
Department
Course
Professor
Document Summary
Possible to write depth and breadth first search with identical code, just different data structures. 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. Performs modified bfs that accounts for edge weights; uses priority queue instead of a queue. 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, Insert record for each vertex into pq, record contains:
