Graphs at Work

Graphs at Work: The Fastest Drive, Not the Fewest Roads: Dijkstra's Algorithm, Which Course First? Topological Sort.

Updated

  1. The Fastest Drive, Not the Fewest Roads: Dijkstra's Algorithm (Freelancer): Find the fastest route through a town where every road takes a different number of minutes: why counting roads, always taking the shortest next road and trying every route all fail, and the algorithm a GPS uses instead, Dijkstra's algorithm, made fast by a priority queue.
  2. Which Course First? Topological Sort (Freelancer): Plan an order for a student's courses where every prerequisite comes first, fast even for a huge catalog, and spot the loop of prerequisites that makes any order impossible: why alphabetical order, sorting by prerequisite count and rescanning the catalog all fall short, and the method that fixes them, a topological sort.