The diagram below shows an input network for the minimum-cost flow problem, and the flow (shown in red) in this network at the end of the 2-nd iteration of the Successive Shortest Path algorithm. During the computation, whenever there is a choice of a vertex, the algorithm selects the vertex which is first in the lexicographical order. (This means, for example, that during the first iteration, the algorithm selected vertex p1 from the two available supply vertices, and selected vertex r1 from the two available demand vertices.) Complete the following statements by dragging and dropping appropriate options.There was  Blank 1 Question 1 path from p2 to r1 in the residual network at the beginning of the 2-nd iteration.At the end of the 2-nd iteration, the flow saturates  Blank 2 Question 1 edges.At the beginning of the 3-rd iteration, the residual supply at vertex p2 is  Blank 3 Question 1 .In the residual network constructed in the 3-rd iteration,  Blank 4 Question 1 vertices are reachable from vertex p2.The cost of the path selected in the residual network in the 3-rd iteration is  Blank 5 Question 1 .The flow in the input network computed by the end of the 3-rd iteration  Blank 6 Question 1 satisfy all supply and demand.

The maximal flow solution algorithm allows the user to choose a path through the network from the origin to the destination by any criteria.Group of answer choicesTrueFalse

5.2-2. Dijkstra’s link-state routing algorithm. Consider Dijkstra’s link-state routing algorithm that is computing a least-cost path from node a to other nodes b, c, d, e,  f.  Which of the following statements is true.  (Refer to Section 5.2 in the text for notation.)Group of answer choicesSuppose nodes b, c, and d are in the set N’.  These nodes will remain in N’ for the rest of the algorithm, since the least-cost paths from a to b, c, and d are known.The values computed in the vector D(v), the currently known least cost of a path from a to any node v, will always decrease following an iteration.Following the initialization step, if nodes b and c are directly connected to a, then the least cost path to b and c will never change from this initial cost.The values computed in the vector D(v), the currently known least cost of a path from a to any node v, will never increase following an iteration.In the initialization step, the initial cost from a to each of these destinations is initialized to either the cost of a link directly connecting a to a direct neighbor, or infinity otherwise.

Which of the following is not an assumption of a minimum-cost flow problem?A) At least one of the nodes is a supply node.B) There is an equal number of supply and demand nodes.C) Flow through an arc is only allowed in the direction indicated by the arrowhead.D) The cost of the flow through each arc is proportional to the amount of that flow.E) The objective is either to minimize the total cost or to maximize the total profit.

The source node is the input node in a maximal flow problem.Group of answer choicesTrueFalse

Consider the following input for the minimum-congestion multicommodity flow problem: the flow network as given below and 2 commodities (s1, t1, 40) and (s2, t2, 80).The current simultaneous flow sends 30 units of commodity 1 along path (s1, a, b, t1) , 10 units of commodity 1 along path (s1, c, e, t1), 40 units of commodity 2 along path (s2, c, e, t2) and 40 units of commodity 2 along path (s2, p, q, t2).Complete the following statements by dragging and dropping appropriate options.