October 15, 2025

Topics of the day

• Dijkstra's algorithm
• Using priority queues

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)
• priority_queue in C++ (en.cppreference.com)
• PriorityQueue in Java (docs.oracle.com)
• queue.PriorityQueue in Python (docs.python.org)

Questions and exercises

1. What problem does Dijkstra's algorithm solve? What kinds of graphs can/can't it be used on?
2. 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?
3. 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.
4. In your preferred language (not necessarily C++ or Java), how does the built-in priority queue type know how to order its contents? (That is, how does it decide what has the highest priority?)

Assignments

Today

• Project 3: A* out

Upcoming

• Homework 4 due (20 Oct)
• Project 3: A* prep due (22 Oct)