0 votes 0 votes Which of the following statements is true? Adding a constant to every edge weight in a directed graph can change the set of edges that belongs to minimum cost spanning tree. Assume unique weights. Complete graph with 4 vertices, each edges having same weights can have maximum 28 minimum cost spanning tree. Rerunning Dijkstra’s algorithm on a graph V times will result in the correct shortest paths tree, even if there are negative edges (but no negative cycles). None of these how is 3rd wrong? If there is no negative cycles dijkstra can work just fine right? Algorithms made-easy-test-series algorithms dijkstras-algorithm + – S Ram asked Jan 24, 2017 • retagged Jul 8, 2022 by Lakshman Bhaiya S Ram 589 views answer comment Share Follow See 1 comment See all 1 1 comment reply nitish1995 commented Apr 8, 2017 reply Follow Share @ S Ram...if there are negative weight cycles than dijkstra will surely fail but if there are negative weight edges(need not be cycle) then dijkstra may or may not fail. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes No. Dijkstra may give incorrect result if negative edges are present. Then we use Bellman-Ford, and it may fail in case of negative edge weight cycles. Lucky sunda answered Jan 29, 2017 Lucky sunda comment Share Follow See all 0 reply Please log in or register to add a comment.