MST with modification

algorithm, graph-algorithm, kruskals-algorithm, minimum-spanning-tree

Solution

I might be confusing, but as far as I remember, kruskal can handle negative weights,so you can give this edge `-infinity` weight.

- Of course it won't actually be `-infinity`, but a number low enough to be significant enough that it cannot be ignored, something like `-1 * sigma(|weight(e)|)` for each e in E.

Problem

Can anyone think of a way to modify Kruskal's algorithm for a minimum spanning tree so that it must include a certain edge (u,v)?

Original source