In the statements below, the 'SSP algorithm' stands for the Successive-Shortest-Path algorithm for the minimum-cost flow

[answerhappygod]

In The Statements Below The Ssp Algorithm Stands For The Successive Shortest Path Algorithm For The Minimum Cost Flow 1 (132.87 KiB) Viewed 18 times

In the statements below, the 'SSP algorithm' stands for the Successive-Shortest-Path algorithm for the minimum-cost flow problem. The terms n and m refer to the number of vertices and the number of edges, respectively, in the input network, and we assume that m > n. Select all correct statements. Select one or more: □ If all input edge capacities are equal to 1 and all node supplies/demands are integer numbers, then the number of iterations in the SSP algorithm is O(m), but not necessarily O(n). The amount of flow which is sent in the current iteration of the SSP algorithm may be less than the residual capacity of the selected path. O The running time of each iteration of the SSP algorithm is dominated by the computation of the residual network. During the execution of the SSP algorithm, the residual supply of a supply vertex never increases. □ If all input edge capacities and node supplies/demands are integer numbers, the sum of the supplies is equal to 100 and the sum of the demands is also equal to 100, then the number of iterations in the SSP algorithm is at most 100 times m, but can be greater than 100 times n. The amount of flow which is sent in the current iteration of the SSP algorithm is always equal to the residual capacity of the path selected in this iteration. O None of the other statements is correct. During the execution of the SSP algorithm, the residual capacity of an edge never increases. If all input edge capacities and node supplies/demands are integer numbers, the sum of the supplies is equal to 100 and the sum of the demands is also equal to 100, then the number of iterations in the SSP algorithm is at most 100. 0 n each iteration of the SSP algorithm, the constructio the dual network takes 0(m If all input edge capacities are equal to 1 and all node supplies/demands are integer numbers, then the number of iterations in the SSP algorithm is O(n). The SSP algorithm can be implemented in such a way that the total running time is O(nm log n).