Day 20：Dijkstra演算法

先前我们利用广度优先搜寻，找到图中两节点之间的最短路径，其中所谓「最短」是指「经过最少的边」。可是这样的路径却未必是最快路径，因为现实生活中不会每条路径的距离或交通状况都一样。如果想要像一个聪明的导航系统，找出最快的路径该怎麽做呢？

我们先想像在图的边上面加上数字，也就是所谓的权重(weight)，边上有权重的图叫做赋权图或加权图(weighted graph)。权重可以视为是经过一条边所需的成本，在实际问题中它可以代表距离、时间、金钱等各种意义。

图片来源：GeeksforGeeks

利用Dijkstra演算法，可以在赋权图中找出成本最低，即权重总和最小的路径，下述例子以距离最短表达，当然权重实际代表意义可能依问题改变。

Dijkstra演算法的方法是从起始节点开始，每次选择距离最近的节点，并且逐步更新起点到各节点的最短距离。

以上方的图来说，假设我们要从0到3，我们可以先把起始点到所有节点的距离暂时定为无穷远，因为目前尚不知道到任何节点的距离。

首先检查起点的邻居，若无目标节点，将起点与邻居的距离更新。

接着进行几个步骤：

1. 选择目前距离起点最近的节点n，计算起点经过节点n到所有节点n邻居的距离，如果比纪录中的当前距离短，就更新资料。
2. 计算完所有邻居的距离，节点n就算是已访问过，之後不必再检查。
3. 重复上述步骤，直到目的地节点已被访问，或者未访问节点的距离都是无穷远(没有路径存在)。

根据纪录，我们选择目前最近的节点1，起点经过节点1到邻居4, 3, 2的距离分别是60, 50, 40，接着可以更新表格。其中到达4的距离为60，并没有比原本的纪录20短，所以不更新。最後将1标为已访问。

接着选择当前最近的节点4，重复上面的步骤，有较短路径即更新表格。以4来说，经过4到达节点3的距离为90，不更新资料。

以此类推，最终直到目标节点3也被访问後，如下表格中0到3的距离50即是到目的地的最短距离。

当然此处只是记录了距离，如果想要知道中间的路径，则可以每当更新最短距离的时候也记录该节点的父节点，最後由终点回溯每一个节点的父节点直到起点，即为最短距离的路径。例如更新节点1距离时记录父节点为0，更新节点3距离时记录父节点为1，最後从3回推最短路径为0-1-3

Dijkstra演算法还有很多的变化型，也可以用在有向图上，但基本上没有办法操作有权重为负值的图(除非多次访问节点，但这也就降低了执行效率)。要操作有负权重的图可以参考Bellman–Ford演算法。

Dijkstra演算法的执行时间取决於操作时的资料结构，如果是使用阵列来储存节点，执行时间为O(|V|²)，但如果改成使用堆积，执行时间可以缩短为O(|E|+|V| log |V|)。