狄克斯屈拉Dijkstra标号算法.pptx

文档介绍：标号算法的基本原理回顾如图v1→v2→v3→v5是v1→v5的最短路,则v1→v2→v3一定是v1→v3的最短路,v1→v2也一定是v1→v2的最短路。v1v2v3v5v421015378v1,6v5v223464v3v1v4121061210v8v9v72363v60,0M,∞M,∞v1,3M,∞M,∞M,∞v1,1v1,1永久标号临时标号例:用标号算法求v1出发到v8,使总费用最小的旅行路线。标号算法计算过程示例0,0v1,6v5v223464v3v1v4121061210v8v9v72363v60,0M,∞M,∞v1,3M,∞M,∞M,∞0,0v1,1v4,11v1,3标号算法计算过程示例v5v223464v3v1v4121061210v8v9v72363v60,0M,∞v1,1M,∞M,∞M,∞1,3v4,11v1,3v1,6v3,5v3,5标号算法计算过程示例v5v223464v3v1v4121061210v8v9v72363v60,0M,∞v4,11v1,1M,∞M,∞M,∞v1,3v3,5v2,6v2,6标号算法计算过程示例v5v223464v3v1v4121061210v8v9v72363v60,0M,∞v4,11v1,1M,∞M,∞v1,3v5,12v5,9v5,9v3,5v2,6v5,10标号算法计算过程示例v5v223464v3v1v4121061210v8v9v72363v60,0v5,10v1,1M,∞v5,12v1,3v5,9v3,5v2,6v5,10标号算法计算过程示例v5v223464v3v1v4121061210v8v9v72363v60,0v1,1M,∞v5,12v1,3v5,9v3,5v2,6v5,10v5,12标号算法计算过程示例v5v223464v3v1v4121061210v8v9v72363v60,0v5,10v1,1M,∞v5,12v1,3v5,9v5,12v3,5v2,6v5,10标号结束反向追踪v1出发到v8总费用最小为12,旅行路线为v1,v3,v2,v5,v8标号算法计算过程示例THANKSFORYOURATTENTION