Negative weights
Task number: 4233
Decide whether Kruskal’s algorithm will work correctly on graphs with negative weights on edges, or whether it will fail on one of these.
Solution
The algorithm does not fail. If \( c \) is the smallest weight, then if we increase the weights by \( -c \), we get a graph with non-negative weights and Kruskal’s algorithm does not fail on them. Its execution will be the same as on the original graph.
In fact, only the ordering of the edges according to the weights is important, not the specific values of the weights.
