## Computer Science 136 |

**Lecture 33: Dijkstra's Algorithm, Maps and Dictionaries****Date: December 2, 2005**

- Congratulations to this year's Darwin contest winners:
- Zachary for his creature "Dolly"
- Rhaad for his creature "DumbBit"
- Kyle for his creature "Brainless"

- Lab 10 questions
- Dijkstra'a Algorithm
- The outline from last time:
T is the empty graph; PQ is an empty priority queue; All vertices in V are marked unvisited; Add s to T; mark s as visited in G; Add each edge (s,v) of G to PQ with appropriate value while (T.size() < G.size() and PQ not empty) do nextEdge = PQ.remove(); until(one vertex of nextEdge is visited and the other is unvisited) or until there are no more edges in PQ // assume nextEdge = (v,u) where v is visited (in T) and u is unvisited (not in T) Add u to T; mark u as visited in G; Add (u,v) to T; for each unvisited neighbor w of u add (u,w) to PQ with appropriate weight

- Application to Massachusetts distances example.

- The outline from last time:
- Maps and Dictionaries
- Maps
- Hash Tables

- Spells