Search code examples
algorithmgraphminimum-spanning-tree

Linear algorithm to make edge weights unique

I have a weighted graph, and I want to compute a new weighting function for the graph, such that the edge weights are distinct, and every MST in the new graph corresponds to an MST in the old graph.

I can't find a feasible algorithm. I doubled all the weights, but that won't make them distinct. I also tried doubling the weights and adding different constants to edges with the same weights, but that doesn't feel right, either.

The new graph will have only 1 MST, since all edges are distinct.

Solution

  • Very simple: we multiply all weights by a factor K large enough to ensure that our small changes cannot affect the validity of an MST. I'll go overboard on this one: 

    K = max(<sum of all graph weights>, 
        <quantity of edges>)
        + 1

    Number the N edges in any order, 0 through N-1. To each edge weight, add the edge number. It's trivial to show that

    1. the edge weights are now unique (new difference between different weights is larger than the changes);
    2. any MST in the new graph maps directly to a corresponding MST in the old one (each new path sum is K times the old one, plus a quantity smaller than K -- the comparison (less or greater than) on any two paths cannot be affected).

    Yes, this is overkill: you can restrict the value of K quite a bit. However, making it that large reduces the correctness proofs to lemmas a junior-high algebra student can follow.