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.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email