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 initial state
Step 1 step1
Step 2 step2
Step 3 step3
Step 4 step4
Step 5 step5
Step 6 step6
Notation 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.

  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’?

  3. Riwaj Sapkota says:

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

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>