Your current MST T
contains n-1
edges. The addition to your graph of the new edge e = (u,v)
with weight w
creates exactly one cycle C
in the graph T + e
(T
with edge e
added). If the new edge weight (w
) is less than the weight of the highest-weight edge in this cycle C
, then you can create a lower weight MST by replacing that higher-weight edge with e
. Otherwise, your current MST remains optimal.
The algorithm is basically this:
- Find the unique path
P
fromu
tov
inT
- Find the edge
e*
inP
that has maximum weightw*
- Is
w < w*
?- If so, then
T' = T - e* + e
is the MST forG + e
,
withweight(T') = weight(T) - w* + w
- If not, then
T' = T
is the MST ofG + e
- If so, then