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 |

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

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.

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.

Right, I updated the figure.

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

got it

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

Cool, np