图论动画-基数堆算法.ppt

15.082和6.855J2003年2月25日,基数堆动画,2,从AMO来的例子(有一点小改动),1,0,1,23,47,815,1631,3263,初始化距离标号,把结点插入到桶中.,初始化桶和它们的范围.,2,3,4,5,6,3,选择,1,0,1,23,47,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,选择有最小距离标号的结点,0,2,3,4,5,6,1,4,更新,3,0,1,23,47,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,扫描从结点1出来的弧，更新距离标号.,2,3,4,5,6,1,13,2,0,15,4,20,5,5,选择,3,0,1,23,47,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,选择有最小距离标号的结点,0,6,1,2,4,5,结点3有标号0，它是最小的.,13,0,15,20,3,6,更新,3,0,1,23,47,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,扫描从结点3出来的弧，更新距离标号.,0,6,1,2,4,5,13,0,15,20,3,9,5,7,选择:部分1,0,1,23,47,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,通过从左到右扫描，寻找第一个非空桶.,0,6,1,2,4,13,0,15,20,3,9,5,8,选择:部分2,0,1,23,47,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,通过扫描在桶中的所有的结点，判断在桶中的最小距离值.,0,6,1,2,4,13,0,15,20,3,9,5,d(5)=9,它是最小的.,9,选择:部分3,0,1,23,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,重分配桶5的范围到前4个桶，从值9开始.桶的宽度保持一致，除了一些会变小的桶.,0,6,1,2,4,13,0,15,20,3,9,5,9,10,1112,47,1315,10,选择:部分4,0,1,23,1315,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,重插入结点到正确的桶内.通过向左扫描判定桶.,0,6,1,2,4,13,0,15,20,3,9,5,9,10,1112,4,2,5,在这时候，最左边的桶非空.,11,选择:部分5,0,1,23,1315,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,从最左边的桶选择一个结点.,0,6,1,13,0,15,20,3,9,9,10,1112,4,2,5,5,12,更新,0,1,23,1315,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,扫描从结点5出来的弧，更新距离标号.,0,6,1,13,0,15,20,3,9,9,10,1112,4,2,5,17,6,通过向左扫描，重插入结点到正确的桶中.,13,选择:部分1和2,0,1,23,1315,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,寻找最小非空桶.,0,1,13,0,15,20,3,9,9,10,1112,4,2,5,17,6,在桶里寻找最小距离标号,14,选择:部分3和4,0,1,23,1315,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,重分发在最小桶中桶范围,0,1,13,0,15,20,3,9,9,10,1112,4,2,5,17,6,重插入结点到正确的桶.,13,14,15,2,4,15,选择:部分5,0,1,23,1315,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,从最左桶选择结点.,0,1,13,0,15,20,3,9,9,10,1112,5,17,6,13,14,15,2,4,2,16,更新,0,1,23,1315,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,扫描从结点2出来的弧.,0,1,13,0,15,20,3,9,9,10,1112,5,17,6,13,14,15,4,2,17,选择,修改规则1,0,1,23,1315,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,寻找最小非空桶,0,1,13,0,15,20,3,9,9,10,1112,5,17,6,13,14,15,4,2,如果桶宽度是1，选择在桶中的任何一结点.,4,18,更新,0,1,23,1315,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,扫描从结点4发出的弧,0,1,13,0,15,20,3,9,9,10,1112,5,17,6,13,14,15,2,4,19,选择:修改的规则2,0,1,23,1315,815,1631,3263,1,2,4,5,3,6,13,5,2,8,15,20,9,0,寻找最下非空桶,0,1,13,0,15,20,3,9,9,10,1112,5,17,6,13,14,15,2,4,如果桶内有一单独结点，那么选择该结点.,6,修改的规则和启发式方法在实践中经常很有帮助，但是必须小心使用.,20,算法结束,0,1,23,