Dijkstra在1959年刊登在Numerische Mathematik 1, 269-271的最短路径算法, 题为 A Note on Two Problems in Connexion with Graphs 与前几篇文章所提的似乎有些出入. 或许是原典与後续改善者之间的差别吧. Dijkstra的方法是: 要找到图中P-Q最短路径,则需持续运用同样的算法处理P-R最短路径,R是落在 P-Q最短路径上的一点. 想一想,若R落在P-Q最短路径上,则P-R也须是最短路径, 找到P-Q最短路径的知识,隐含了找到P-R最短路径的知识. 方法如下,先将图分为六群: A 在此的节点都已经知道从P到该点的最短路径长度. B 在此的节点都未决定最短路径,却是下一个可以被选入A的选项 C 其他点 I 在此的边落在P到达A中任一点的最短路径上. II 在此的边是下一个可以被选入I的选项,每条边都连接到B中某一点. III 其他边 算法: 1. 选取下一个点: "Consider all branches r connecting the node just transferred to set A with nodes R in sets B or C." 如果R在B中,就看看r能不能增加P-R最短路径. 如果可以,且短於之前找到另一个 P-R',就以目前的R为选中者. 如果R在C中,就把R移到B,把位於III相关的边移到II. 2. 决定最短路径P-R: 前一步既然选出了候选者,就把选中者R从B移到A,把位於II相关的最短边移到I. 做完之後看看Q是否加入了A,如果是就可以结束,且P-Q最短路径已决定了. 以下是我的操作过程: (P为v1,Q为v9,L(x)是从出发点v1到达x的最短路径) e1 v1 v2 6 初始决定 L(v1)=0 e2 v1 v3 3 e3 v1 v4 9 第三轮决定 L(v3)=3 e4 v2 v5 8 e5 v2 v8 5 e6 v3 v6 2 第六轮决定 L(v6)=5 e7 v4 v5 9 第七轮决定 L(v7)=8 e8 v6 v7 3 e9 v6 v9 8 e10 v7 v9 2 e11 v8 v9 2 第一轮 二轮 三轮 第四轮 第五轮 第六轮 第七轮 A v1 |v1 |v1,v3|v1,v3 |v1,v3,v6 |v1,v3,v6 |v1,v3,v6,v7 B |v2-4 |v2,v4|v2,v4,v6 |v2,v4 |v2,v4,v7,v9|v2,v4,v9 C v2-9 |v5-9 |v5-9 |v5,v7-9 |v5,v7-9 |v5,v8 |v5,v8 I | |e2 |e2 |e2,e6 |e2,e6 |e2,e6,e8 II |e1-3 |e1,e3|e1,e3,e6 |e1,e3 |e1,e3,e8-9 |e1,e3,e9 III e1-11|e4-11|e4-11|e2,e4-5,e7-11|e2,e4-5,e7-11|e2,e4-5,e7 |e2,e4-5,e7 第八轮没有画出来,如果写出来应该是v9移到A,达成结束条件. 在这练习过程我感到一些疑问,Dijkstra方法提出第一步的第一句话说: "just transferred to set A" 照此做下来是greedy方式,但一般我们需要的是dynamic programming方式, 因为,虽然第七轮已经不考虑v2了,但v1-v2长度为6,小於L(v7),则应该先把v2加进来, 不过v2加进来之後反而使产生的P-Q最短路径看起来像一棵树,其中有些支节并不是 最短路径. 随意窜改可能使方法其不一致. 在此讨论谨仅以Dijkstra原论文为主题. 其他书籍所提的方法,日後再讨论比较. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.160.108.251 ※ 编辑: oohay 来自: 218.160.108.251 (02/17 20:46) ※ 编辑: oohay 来自: 218.160.108.251 (02/17 20:47)