Class Notes
(811,155)

Canada
(494,530)

Simon Fraser University
(12,078)

Computing Science
(220)

CMPT 225
(60)

John Edgar
(28)

Lecture

# CMPT 225 Week 11 Lecture 2

Unlock Document

Simon Fraser University

Computing Science

CMPT 225

John Edgar

Summer

Description

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