Heuristic Method for Traffic Maximization
Assigning the maximum possible amount of traffic between two locations (A and F) can be solved heuristically:
  • Step 1. Identify all possible paths between two locations. On the above example, there are 3 possible paths between A and F.
  • Step 2. Select a path and assign the maximum traffic that the link having the weakest capacity can support. In this case, the maximum amount of traffic that path A-B-D-F can support is 20 units. Subtract this number from the capacity of every link on this path. This subtraction cannot be lower than 0. The result of this subtraction is the remaining traffic capacity of each links of the path.
  • Step 3. Repeat the same procedure for all possible paths until there is no more capacity left.
  • Step 4. Once there is no more capacity left, the number at the destination node is the maximal traffic the network can support, which in this case are 50 units.