Heuristic Method for Traffic Maximization

The above figure shows a problem of assigning the maximum possible amount of traffic between two locations; a and f. The method works as follows:

• Identify all possible paths between two nodes (1).
• Select a path and assign the maximum traffic that the link having the weakest capacity can support (2). In this case, the maximum amount of traffic that the link a-b-d-f can support is 20.
• Subtract this number from the capacity of every link in this path (2). This subtraction cannot be lower than 0. The result of this subtraction is the remaining traffic capacity of each links of the path.
• Repeat the same procedure for all possible paths (3 and 4). The number at the destination node is the maximal traffic the network can support between two places (4), in this case 50 units.