分支限界法求最短路径举例 赋权图G Open表 Closed表 [5,60,3] 1,0,0] 100 [2,10,1 30 2 4,30,1] 50 [3,50,4 60 4 取出[5,60,3],因其已经是目标结点,算法成 功并终止。 依据逆向指针可得最短路径为1→4→3→5。 2021/221 计算机算法设计与分析2021/2/21 计算机算法设计与分析 7 分支限界法求最短路径举例 1 2 5 3 4 10 20 50 100 30 10 60 赋权图G 初始时，将源[1, 0, 0]放入Open，Closed为空。 Open表 [1, 0, 0] Closed表 取出[1, 0, 0]放入Closed；生成其后继[2, 10, 1]、 [4, 30, 1]和[5, 100, 1]，并依序放入Open。 [5, 100, 1] [1, 0, 0] [4, 30, 1] [2, 10, 1] 取出[2, 10, 1]放入Closed；生成其后继[3, 60, 2]， 并依序插入Open。 [3, 60, 2] [2, 10, 1] [4, 30, 1] 取出[4, 30, 1]放入Closed；生成其后继[3, 50, 4] 和[5, 90, 4] ，修订Open中已有的两个结点并依 序排列。 [4, 30, 1] [5, 90, 4] [3, 50, 4] 取出[3, 50, 4]放入Closed；生成其后继[2, 100, 3] 和[5, 60, 3]，前者因劣于Closed中的[2, 10, 1]而 被抛弃，后者修订了Open中的[5, 90, 4]。 [3, 50, 4] [5, 60, 3] 取出[5, 60, 3]，因其已经是目标结点，算法成 功并终止。 依据逆向指针可得最短路径为1→4→3→5