Paul's Python CoursePPC

Dijkstra's algorithm

Not met yet

Dijkstra's algorithm finds the quickest route in a weighted graph. Keep a heap of (minutes, place) waiting to be looked at. Take the nearest; if it's already settled, skip it, because it's an old entry. Otherwise settle it: nothing found later can be quicker, since every other waiting place is at least as far and no road takes less than 0. Then for each road out, if going this way beats the best time so far, note it and push it. Note where each best time came from to walk the route back. With a heap it's O((places + roads) log places). Negative weights break it.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks a place's distance is final the first time it is reached, as it is in breadth-first search.
  • Thinks pushing a place onto the heap again with a better time removes its old entry.
  • Thinks Dijkstra's algorithm still gives the right answer when some roads have negative weights.
  • Thinks Dijkstra's algorithm settles places in order of how many roads away they are, rather than how far.

Where it comes up