October 9, 2023
Monday of Week 8
Topic of the day
- Dijkstra's algorithm
Suggested reading
- Section 9.3.2 from Mark Allen Weiss, Data structures and algorithm analysis in C++, 3e
Online references
- Dijkstra's algorithm (en.wikipedia.org)
- Dijkstra example (graphical) (www.geeksforgeeks.org)
- Dijkstra example (good pseudocode, great data trace) (stackoverflow.com)
Questions and exercises
- What problem does Dijkstra's algorithm solve? What kinds of graphs can/can't it be used on?
Consider the graph to the right. Treating node H as the source or starting point, in what order would Dijkstra's algorithm visit the nodes? Why?
- Take one of the examples from the readings and show some aspect of it that isn't shown in the reading. For example, draw the graph for the one that doesn't show the drawing of the graph, or show the trace of values of one of the data structures for the ones that don't show those.
Assignments
Today
- Exam 1 due
- Project 3: A* out
Upcoming
- Project 3: A* prep due (16 Oct)
