# Example of updating a MST

Needed to draw an example for a Stackoverflow question, so the pictures goes here in case anyone else could use them.
Please make a comment if you see a mistake.

The images illustrates the Insert algorithm from this paper.

Post will be updated with more details soon.

 Initial MST Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Notation
This entry was posted in algorithms and tagged , , , . Bookmark the permalink.

### 8 Responses to Example of updating a MST

1. Riwaj Sapkota says:

Been trying to follow on paper the whole day. I am going through your illustration to understand it better. What I don’t understand is how on step 2 you update T to (C,D). Perhaps, I did not understand if t<—m is outside the for loop or inside it. But, thank you once again

• Jacob Midtgaard-Olesen says:

I believe that t<-m is outside the loop since it has the same indentation as the loop header.

And so, in step 2 there are no edges from the old MST to examine, so we move directly to assigning t to m which is (C,D).

Note that c(X,Y) where X,Y have no edge in G would, as I see it, return an infinitely high value. I don’t think this is explained very well, but that explains why m <- (r,z) always makes sense, as c(r,z) will just return an infinitely high value if the edge is not there.

• Riwaj Sapkota says:

I got that one right. I think there is a slight mistake in step 5. It should be k= max of BD and AB and h= min of BD and AB.

• Jacob Midtgaard-Olesen says:

Right, I updated the figure.

2. Riwaj Sapkota says:

One last query– why is t=(C,D) and m =(C,D) in step 5? I did not get what it means by ‘looping’?

• Riwaj Sapkota says:

got it

3. Riwaj Sapkota says:

With your example, I was able to implement the algorithm. Thank you once again

• Jacob Midtgaard-Olesen says:

Cool, np