图论动画-Dijkstra算法剖析.ppt

15.082 和 6.855J  Dijkstra 算法 一个例子 更新步 选择最小临时标号 更新步 选择最小临时标号 更新 选择最小临时标号 更新 选择最小临时标号 更新 选择最小临时标号 结束算法 * * 1 2 3 4 5 6 2 4 2 1 3 4 2 3 2 初始化 1 0 ? ? ? ? ? 选择有最小临时距离标号的结点. 2 3 4 5 6 2 4 2 1 3 4 2 3 2 2 4 0 ? ? ? ? ? 1 1 3 4 5 6 2 4 2 1 3 4 2 3 2 2 4 0 2 ? ? ? 1 2 3 4 5 6 2 4 2 1 3 4 2 3 2 2 4 6 4 3 0 ? ? ? 结点 3 的前驱现在是结点 2 1 2 4 5 6 2 4 2 1 3 4 2 3 2 2 3 6 4 0 ? 3 1 2 4 5 6 2 4 2 1 3 4 2 3 2 0 d(5) 没有变化. 3 2 3 6 4 ? 1 2 4 6 2 4 2 1 3 4 2 3 2 0 3 2 3 6 4 ? 5 1 2 4 6 2 4 2 1 3 4 2 3 2 0 3 2 3 6 4 ? 5 d(4)没有变化 6 1 2 6 2 4 2 1 3 4 2 3 2 0 3 2 3 6 4 5 6 4 1 2 6 2 4 2 1 3 4 2 3 2 0 3 2 3 6 4 5 6 4 d(6) 没有改变 1 2 2 4 2 1 3 4 2 3 2 0 3 2 3 6 4 5 6 4 6 没有要更新的了 1 2 2 4 2 1 3 4 2 3 2 0 3 2 3 6 4 5 6 4 6 现在所有结点都保持不变了 前驱形成了树 从结点 1 到结点 6 的最短路径能通过回溯前驱得到 Obtain a network, and use the same network to illustrate the shortest path problem for communication networks, the max flow problem, the minimum cost flow problem, and the multicommodity flow problem. This will be a very efficient way of introducing the four problems. (Perhaps under 10 minutes of class time.) * *