Sample applications

1. Given a list of connected pipes with different flow-capacities, find the amount of water that can go from a starting point to a given ending point.

2. You have a lot of cars that you want to take from city ‘s’ to city ‘t’. Each road between two cities has a limit on the number of cars that can go there. What is the maximum number of cars that you can take from ‘s’ to ‘t’?

The two above problems can be visualized in the following way:

Image for post
Image for post
Figure 1.

In Problem 1, each letter represents a pipe, and each number represents the flow-capacity between two pipes. That is, maximum amount of water that can go from s to a is 11 units, a to b is 12 units and so on. …

About

Lazaron Shyta

Computer Science student with a love for solving complex problems.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store