Ta dựng cây khung có trọng số lớn nhất của đồ thị (Kruskal, Prim...)

Xét từng cạnh \((u,v)\) không có trên cây khung. Đây chính là những cạnh ta cần nâng cấp.

Chứng minh : Giả sử \(e_1, e_2, e_3, .., e_k\) là các cạnh trên đường đi từ \(u\) đến \(v\) của cây khung. Để thuận tiện, ta kí hiệu \(w(A)\) là trọng số cạnh \(A\) và \(dist(u,v) = min(w(e_1), w(e_2), .., w(e_k))\)

Hiển nhiên ta có \(dist(u,v) \geq w((u,v))\). Nếu \(w((u,v)) > dist(u,v)\), ta hoàn toàn có thể thay một cạnh trên đường đi từ \(u\) đến \(v\) thành cạnh \((u,v)\) để được một cây khung có trọng số lớn hơn. Điều này vô lí vì cây khung ta đã tạo ra có trọng số lớn nhất có thể.

Lượng chi phí nâng cấp đúng bằng \(\sum dist(u,v) - w(u,v)\) với mọi cạnh \((u,v)\) không thuộc cây khung. Tức là, tăng \(w(u,v)\) lên giá trị \(w'(u,v) = dist(u,v)\).

Đây cũng chính là chi phí nhỏ nhất mà ta cần để nâng cấp mạng :

• \(w'(u,v) = dist(u,v)\) nên mọi đường đi từ \(u\) tới \(v\) đều thỏa mãn yêu cầu đề bài.
• Giả sử ta tăng \(w'(u,v) > dist(u,v)\). Khi đó, nếu trên đường đi từ \(u\) đến \(v\) trên cây khung tồn tại cạnh \(e\) có \(w(e) < w'(u,v)\), ta lại phải nâng trọng số của \(w(e) \geq w'(u,v)\), và vì vậy tốn chi phí không cần thiết.

Phần tính dist(u,v) hoàn toàn có thể dùng LCA.