The statements below refer to Single-Source Shortest-Paths algorithms. The terms n and m refer to the number of vertices

[answerhappygod]

The Statements Below Refer To Single Source Shortest Paths Algorithms The Terms N And M Refer To The Number Of Vertices 1 (155.02 KiB) Viewed 18 times

The statements below refer to Single-Source Shortest-Paths algorithms. The terms n and m refer to the number of vertices and the number of edges, respectively, in the input graph. Select all correct statements. Select one or more: If each edge weight is equal to 0, 1, or 2, then at each point during the computation of Dijkstra's shortest-path algorithm, the priority queue contains at most 3 entries with finite values (but may contain also a number of entries with the 'infinity' value). The running time of the Bellman-Ford shortest-path algorithm with FIFO queue and a cycle detection procedure which runs in O(n) time and is executed every n iterations of the main loop, is O(nm). A single-source shortest-paths algorithm which is based on the relaxation technique uses only two arrays, one for the shortest-path estimates and one for the predecessor (parent) vertices, and does not use any other data structures. None of the other statements is correct. The running time of the Bellman-Ford shortest-path algorithm with FIFO queue and a cycle detection procedure which runs in O(n) time and is executed every n iterations of the main loop, is O(n²m) but not necessarily O(nm). Assuming that the input graph does not have negative edge weights, during the computation of Dijkstra's shortest-path algorithm with the Heap implementation of the priority queue, the total time spent on the Extract-Min operations is O(n log n). A single-source shortest-paths algorithm which is based on the relaxation technique uses two arrays, one for the shortest-path estimates and one array for the predecessor (parent) vertices, and may use additional data structures. Assuming that the input graph does not have negative edge weights, during the computation of Dijkstra's shortest-path algorithm with the Heap implementation of the priority queue, the Heap-Decrease-Key operation is executed O(m) times. If each edge weight is equal to 0, 1, or 2, then at each point during the computation of Dijkstra's shortest-path algorithm, the entries in the priority queue have at most 3 distinct finite values (but may also have the 'infinity' value). Assuming that the input graph does not have negative edge weights, during the computation of Dijkstra's shortest-path algorithm with the Heap implementation of the priority queue, the total time spent on the Extract-Min operations is 0(m log n) but not necessarily O(n log n). Assuming that the input graph does not have negative edge weights, Dijkstra's shortest-path algorithm with the Heap implementation of the priority queue executes in the worst-case (m log n) Relax operations.