CS 2213/2211
|
![]() |
![]() | |
Figure 0 | Figure 1 | |
---|---|---|
![]() |
![]() | |
Figure 2 | Figure 3 | |
![]() | ![]() | |
Figure 4 | Figure 5 |
Note: above, at each step another vertex u has status[u] changed for 0 to 1. At this point its circle is drawn in red. At the end, all vertices are taken care of.
Initial Graph: g[0]: --> (3,5) --> (1,10) --> NULL g[1]: --> (3,2) --> (2,1) --> NULL g[2]: --> (4,4) --> NULL g[3]: --> (4,2) --> (2,9) --> (1,3) --> NULL g[4]: --> (2,6) --> (0,7) --> NULL Initial Diagram, Figure 0 above. Result After 1st Step, Figure 1 above: u = 0, shortest[u] = 0 New shortest: w:3, shortest[w]: 5 New shortest: w:1, shortest[w]: 10 Result After 2nd Step, Figure 2 above: u = 3, shortest[u] = 5 New shortest: w:4, shortest[w]: 7 New shortest: w:2, shortest[w]: 14 New shortest: w:1, shortest[w]: 8 Result After 3rd Step, Figure 3 above: u = 4, shortest[u] = 7 New shortest: w:2, shortest[w]: 13 Result After 4th Step, Figure 4 above: u = 1, shortest[u] = 8 New shortest: w:2, shortest[w]: 9 Result After 5th Step, Figure 5 above: u = 2, shortest[u] = 9 Final Results: 0: shortest[i]: 0 1: shortest[i]: 8 2: shortest[i]: 9 3: shortest[i]: 5 4: shortest[i]: 7