拥抱「资料结构」的「演算法」(29) - 戴克斯特拉演算法求最短路径

前言

对图形的搜寻有了基本观念之後，接下来要在图形的边加入权重的部分，这样就能找到最短路径

生活常识

你有自己规划行程的经验吗？如果朋友住在台中住在想去花莲旅游，那麽你会怎麽建议行程呢？是建议从南投走横贯公路，还是从绕到台北宜兰，还是打开 googe map 直接看哪个路径比较短，或是花费的时间比较少，由下图可以看到 google map 推荐路程时间最少的(走往台北的路径)，而不是距离最短的路径(走往南投的路径)

专业知识 - 戴克斯特拉演算法 Dijkstra's algorithm

戴克斯特拉演算法因为音译的关系有蛮多种说法的，每一种名字都蛮常的XD，我自己是比较习惯用英文记忆XD，回归正题，如果仅以边作为挑选路径的考量，也就是图形中 A 点到 B 点经过几个边，可以使用昨天介绍的广度或深度演算法，但如果加上时间的考量，则广度搜寻演算法的结果并不一定会等於戴克斯特拉演算法的结果

如下图，起点为 A 点，目的地为 E 点：

• 左图
  没有时间的权重，所以最短路径会选 ACE，此路段最少，因为只需要经过2个边

• 右图
  加上时间的权重，单位为分钟，ACE 花费时间为 13(9+4) 分钟，虽然 ABDE 要走 3 个边但只需要花 10 分钟，所以走 ABDE 最快

最短路径 Single-Pair Shortest Path

有一个有向加权图形 G = ( V, E )，最短路径为图中两顶点间的最短路径，也就是权重加总数值最小者，其中加权的部分，就看个人的考量，也许是时间，或是开车油钱等等

例子

以下图为例，权重为公里，想要找到 A 到任一点最短的路径，透过戴克斯特拉演算法要如何取得结果，这边要特别注意，使用戴克斯特拉演算法时，图形中的权重不能有负数(正负数)，否则演算法的结果可能会有错误，须改用其他演算法，像是贝尔曼福特演算法(Bellman-Ford algorithm)

先来看搜寻结果，稍後会有详细的步骤说明

可由步骤 5 观察到，A 到任一点的最短距离
A 到 A 的最短距离为 0
A 到 B 的最短距离为 1
A 到 C 的最短距离为 4
A 到 D 的最短距离为 6
A 到 E 的最短距离为 6

步骤说明：

1. 寻找与 A 到相邻的点 B 与 C 的最短路径
   A 到 B 点：1 公里
   A 到 C 点：5 公里
   此时不知道 D 与 E 距离 A 多远，所以先画 - 符号表示无穷大

2. 寻找与 B 到相邻的点 C 与 D 的最短路径
   A 到 C 点：上个步骤的 A 到 C 是 5 公里，但 A 经过 B 在到 C 的距离更短，只需要 4 公里，所以将 A 到 C 的距离更新为 4
   A 到 D 点：A 到 D 点的距离为 6 = 1( A 到 B ) + 5( B 到 D)，将表格中的 - 符号更新为 6

3. 寻找与 C 到相邻的点 E 的最短路径
   A 到 E 点：先查询表格，A 到 C 的最短距离计算的结果为 4 公里( A 到 B 再到 C)，C 到 E 的距离为 2 公里，所以 A 到 E 的最短距离为 6 ( 2 + 4 ) 公里

4. 寻找与 D 到相邻的点 E 的最短路径
   A 到 E 点：先查询表格，A 到 D 的最短距离为 6 公里，D 到 E 为 4 公里，所以 A 经过 D 再到 E 的路径为 10 ( 6 + 4 ) 公里，但与第 3 步骤的 A 到 E 中间通过 C 点比较，发现 10 大於 6 ，所以 10 不是最短路径，不更新表格数值

5. 寻找与 D 到相邻的点 E 的最短路径
   E 点没有相邻顶点，结束搜寻，如果表格中还含有 - 符号，代表 A 到无法抵达此点

今日小结

执行戴克斯特拉演算法，在计算过程中，我们需要去取得资料并记录结果，这个过程需要到记忆体空间，也就是如何将这些资料储存起来，会使用到之前提到的资料结构，你会选择那些资料结构来搭配这个演算法呢？其实之前的章节都有说过，不访动动脑想想看哦

今日谜题

小美要从丹麦(Danmark)到澳洲(Austria)找一个人，下图是任意门的传送点与路径，上面是标注每条路线要走几公里才能抵达下一个任意门，你可以帮小美找出最短路径吗？这条最短路径似乎按藏着关於小美要找的人的讯息，你能发现吗？

昨日谜题

谜题说明：利用走梯子游戏来感受一下深度优先搜寻，走访三条路径之後，可以发现只有第一条可以组成一个有意义的单字，答案就是 DEPTH(深度)，你答对了吗