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