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 (199.17 KiB) Viewed 21 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 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. 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. The SSP algorithm can be implemented in such a way that the total running time is O(nm log n). the execution of the SSP algorithm, the residual capacity of an edge never increases. In each iteration of the SSP algorithm, the construction of the residual network takes 0(m) time. The running time of each iteration of the SSP algorithm is dominated by the computation of the residual network. 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. 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). During the execution of the SSP algorithm, the residual supply of a supply vertex never increases. None of the other statements is correct. 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 0(m), but not necessarily O(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.