Lecture 29: DFS vs. BFS, Shortest Paths

CS61B

Summary So Far

Rechability

BFS uses lots of memory for VERY WIDE GRAPH. One vertex connected to 1,000,000 vertices: because it puts lots of stuff on a queue.

DFS uses lots of memory for a spindly graph, because a giant
sequence of recursive in Java uses memory linear in # of recursive calls.

Graph problems so far

quiz:

Dijkstra’s Algorithm

Goal: find the shortest path from the source vertex s to every other vertex.

SPT edge count

Dijkstra's Algorithm

Dijkstra's demo

Dijkstra's runtime

Implementation

Graph Problems so far

Dijkstra's algorithm will find the shortest path from the source vertex to every other vertexes, this will waste a lot of memory in the specific situation:

Video:
Graphs: Dijkstra's Algorithm

Dijkstra Algorithm Example

Shortest Path using Dijkstra's Algorithm

dijkstras-shortest-path-algorith

DijkstraSP.java

自己试着做一遍：

A*

we don't want to find the shortest path from vertex to every other vertex, but only want to find one target.

D(denver, NYC) = d(denver, v) + h(v):

Impact of heuristic quality

当h(v)不正确的时候，会得不到正确的答案，这里把h(v)正确叫做：admissible.

A* vs Dijkstra

Graph problem runtime

Extra: A* Properties, Iterative DFS, Kevin Bacon