Dijkstra
Dijkstra on an Erdős-Réyni network with 300 nodes, probability 0.02, and random weights between 1 and 10.
The nodes are the nodes in the heap, to be added to the next paths. The paths are the most recently added shortest distance path to that node. There is an initial exploratory phase where most nodes are mapped out within the first few cycles, and then there is a mild "correction" phase where slightly more optimal paths are found. After that, the optimal path to a node will likely not change.
Odd things I should remind myself of:
- A node will be in the heap at most once.
- The heap is a heap of distances, not nodes. The heap can have multiple entries of the same value, representing different paths to different nodes with the same distance.
- The heap will never have multiple distances to the same node.