DSC 40B

Dijkstra's Algorithm

Instructions: Choose a graph, then click the buttons (or press the ← and → keys) to step through Dijkstra's algorithm one change at a time: a call to extract_min, which takes the node with the smallest estimate out of the priority queue, or one change made by a call to update along an edge out of that node. Uncheck Small steps under Options to take each call to update in a single step.

The number next to each node is its estimated distance from the source, est, and the purple arrows point to each node from its estimated predecessor. Nodes that have been taken out of the priority queue are visited; these make up the set C from lecture. The node whose edges are being updated is circled, and the edge being updated is drawn in bold.

The priority queue is drawn below the graph, smallest priority first: each node's priority is its estimate, shown under it. When an update lowers a node's estimate, its priority changes too, with change_priority.

Dijkstra's algorithm assumes that every edge weight is positive. Choose the Negative edge weight graph to see what goes wrong when one isn't, and check Mark correct estimates under Options to see which estimates are correct at each step.

Options

2 estimated distance estimated predecessor visited

What happened