Question

Your colleague has provided you a program for finding a minimum spanning tree (mst) for a weighted simple graph. Unfortunately it rejects your input graph since your graph has edges that have negative weights, and the program only accepts graphs with non-negative-weight edges. Explain how you can still use her program for finding an mst for your graph. Assume that you do not have access to the program's source code.

Answer 1

it is true that for finding an mst of a graph we must have positive edges in our graph. so the problem arises only due to the negative edges present in the graph. while giving the input just add a constant K (any positive integer ) to all the edges such that all edges becomes positive when this constant K is added.

so once all edges becomes positive ,the output will be fine . because the problem of negative edges just vanishes from the graph. hence no need to access source code .

Thankyou hope it works.