The Gateway to Computer Science Excellence
+2 votes
Suppose we have a graph with negative edge weights. We take the largest magnitude negative edge weight -k and reset each edge weight w to w+k+1. Which of the following is true?
 1. Kruskal's algorithm will identify the same spanning tree on the new graph as on the old graph.
 2. Minimum cost spanning trees in the original graph will not correspond to minimum cost spanning trees in the new graph.
 3. Prim's algorithm will not work on the original graph but will work on the modified graph.
4.  There are more minimum cost spanning trees in the modified graph than in the original graph.

is the correct answer 3 ?
in DS by (31 points) | 607 views
Option 1 is true

1 Answer

+1 vote
I think ans is 1 (A)

In Kruskal's algorithm the safe edge added to A (subset of a MST) is always a least weight edge in the graph that connects two distinct components. So, if there are negative weight edges they will not affect the evolution of the algorithm.
by (27 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,662 questions
56,122 answers
93,028 users