Class Meeting 12B

Today we will finish off our discussion of depth first search to solve Sudoku puzzles. Then we will talk about shortest path search using Dijkstra’s algorithm and priority queues.

Download the Slides from today

Topics for today’s lecture

• TBA

Links for today

• Dijkstra’s Algorithm.

  • Graphical explanation of Dijkstra’s algorithm.

  • Another graphical explanation of Dijkstra’s algorithm.

  • Build your own grid and run Dijkstra’s algorithm

• Python’s heapq module provides an implementation of a priority queue.

  • There is also the PriorityQueue in the queue module, but that is unnecessarily fancy for our simple Dijkstra’s algorithm. (It allows multiple threads to access the queue at once, which is necessary for parallel programming but not for our single threaded serial program.)

  • Tutorial implementing Dijkstra’s algorithm using heapq. Because there is no way to remove or update an entry in heapq, we may end up removing a node from the queue multiple times; however, that is okay since the first removal will represent the minimum distance / shortest path so subsequent removals can be ignored.

Logistics

There is no repo to clone today!