Omniadisce

Applied maths 19.1: Network flows and shortest paths

Lesson Intermediate

Join free to take this lesson

Anyone can look around, but taking a lesson needs a free account. With one, your answers are checked step by step and your progress is saved, so you can stop and pick up where you left off on any device.

10 steps ยท about 18 min

By the end you can

  • Find a shortest route in a small road network and say why the route with fewest roads can lose
  • Find a project's length as the longest path through its task network, and each task's slack
  • Find the maximum flow through a network and prove it with a minimum cut

Who it is for: You know what a weighted graph is and how Dijkstra's method finds a shortest path (lesson 6.5).

The steps

  1. The bottleneck
  2. Shortest paths, revisited
  3. Shortest delivery route
  4. Projects as networks: the critical path
  5. Earliest finish
  6. How much slack?
  7. Maximum flow and minimum cut
  8. Two separate routes
  9. Find the minimum cut
  10. Where to spend the money

Discussion 0 comments

Log in to join the discussion.

× Enlarged view