Graphs at Work
How a GPS picks the fastest route with Dijkstra's algorithm, and how a college orders its courses so every prerequisite comes first.
Updated
Graphs at Work
- 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.
- 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.
Exercise: Plan Your Class Schedule
- Exercise: Plan Your Class Schedule (Freelancer): A college planning app must tell students what they can take now, an order for every course that keeps each prerequisite first, and how many semesters the degree takes, and spot a catalog mistake that makes any order impossible, fast enough for a catalog of 50,000 courses.