Page 1 of 1
What does the construction of G' by adding s to G with O-weighted outgoing edges to all other vertices in G accomplish i
Posted: Sun May 15, 2022 8:50 am
by answerhappygod
- What Does The Construction Of G By Adding S To G With O Weighted Outgoing Edges To All Other Vertices In G Accomplish I 1 (50.52 KiB) Viewed 46 times
What does the construction of G' by adding s to G with O-weighted outgoing edges to all other vertices in G accomplish in Johnson's algorithm? Check all that result directly from the addition of s and the edges. (Pick carefully, you will get negative points for choosing the wrong answers.) ООООО A. Makes the weights of the graph non-negative so Dijkstra's algorithm applies. B. Computes all pairs shortest paths. C. Ensures that all vertices can be reached by Bellman-Ford to compute h. D. Detects negative weight cycles so that graphs containing them can be rejected. E. Preserves shortest paths: the shortest paths between vertices in G and between these vertices in Gʻare identical.