《算法图解》之狄克斯特拉算法

前言

在学习广度优先搜索的时候，你找出了从A点到B点的路径。

这是最短路径，因为段数最少——只有三段，但不一定是最快路径。如果给这些路段加上时间，你将发现有更快的路径。

如果你要找出最快的路径，该如何办呢？为此，可使用另一种算法——狄克斯特拉算法（Dijkstra’s algorithm）。

使用狄克斯特拉算法

下面来看看如何对下面的图使用这种算法。

其中每个数字表示的都是时间，单位分钟。为找出从起点到终点耗时最短的路径，你将使用狄克斯特拉算法。

如果你使用广度优先搜索，将得到下面这条段数最少的路径。

这条路径耗时7分钟。下面来看看能否找到耗时更短的路径！狄克斯特拉算法包含4个步骤。

(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。

(2) 更新该节点的邻居的开销，其含义将稍后介绍。

(3) 重复这个过程，直到对图中的每个节点都这样做了。

(4) 计算最终路径。

第一步：找出最便宜的节点。

你站在起点，不知道该前往节点A还是前往节点B。前往这两个节点都要多长时间呢？

前往节点A需要6分钟，而前往节点B需要2分钟。至于前往其他节点，你还不知道需要多长时间。

由于你还不知道前往终点需要多长时间，因此你假设为无穷大（这样做的原因你马上就会明白）。节点B是最近的——2分钟就能达到。

第二步：计算经节点B前往其各个邻居所需的时间。

你刚找到了一条前往节点A的更短路径！直接前往节点A需要6分钟。

但经由节点B前往节点A只需5分钟！

对于节点B的邻居，如果找到前往它的更短路径，就更新其开销。在这里，你找到了：

前往节点A的更短路径（时间从6分钟缩短到5分钟）；

前往终点的更短路径（时间从无穷大缩短到7分钟）。

第三步：重复！

重复第一步：找出可在最短时间内前往的节点。你对节点B执行了第二步，除节点B外，可在最短时间内前往的节点是节点A。

重复第二步：更新节点A的所有邻居的开销。

你发现前往终点的时间为6分钟！

你对每个节点都运行了狄克斯特拉算法（无需对终点这样做）。现在，你知道：

前往节点B需要2分钟；

前往节点A需要5分钟；

前往终点需要6分钟。

最后一步——计算最终路径将留到下一节去介绍，这里先直接将最终路径告诉你。

如果使用广度优先搜索，找到的最短路径将不是这条，因为这条路径包含3段，而有一条从起点到终点的路径只有两段。

在前一章，你使用了广度优先搜索来查找两点之间的最短路径，那时“最短路径”的意思是段数最少。在狄克斯特拉算法中，你给每段都分配了一个数字或权重，因此狄克斯特拉算法找出的是总权重最小的路径。

这里重述一下，狄克斯特拉算法包含4个步骤。

(1) 找出最便宜的节点，即可在最短时间内前往的节点。

(2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。

(3) 重复这个过程，直到对图中的每个节点都这样做了。

(4) 计算最终路径。

实现

注意：

狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重（weight）。

如果有负权边，就不能使用狄克斯特拉算法。

下面来看看如何使用代码来实现狄克斯特拉算法，这里以下面的图为例。

要编写解决这个问题的代码，需要三个散列表。

随着算法的进行，你将不断更新散列表costs和parents。首先，需要实现这个图，为此可使用一个散列表。

在前一章中，你像下面这样将节点的所有邻居都存储在散列表中。

graph[“you”] = [“alice”, “bob”, “claire”]

但这里需要同时存储邻居和前往邻居的开销。例如，起点有两个邻居——A和B。

如何表示这些边的权重呢？为何不使用另一个散列表呢？

因此graph[“start”]是一个散列表。要获取起点的所有邻居，可像下面这样做。

有一条从起点到A的边，还有一条从起点到B的边。要获悉这些边的权重，该如何办呢？

下面来添加其他节点及其邻居。

graph[“a”] = {}

graph[“a”][“fin”] = 1

graph[“b”] = {}

graph[“b”][“a”] = 3

graph[“b”][“fin”] = 5

#终点没有任何邻居

graph[“fin”] = {}

表示整个图的散列表类似于下面这样。

接下来，需要用一个散列表来存储每个节点的开销。

节点的开销指的是从起点出发前往该节点需要多长时间。你知道的，从起点到节点B需要2分钟，从起点到节点A需要6分钟（但你可能会找到所需时间更短的路径）。你不知道到终点需要多长时间。对于还不知道的开销，你将其设置为无穷大。在Python中能够表示无穷大吗？你可以这样做：

infinity = float(“inf”)

创建开销表的代码如下：

infinity = float(“inf”)

costs = {}

costs[“a”] = 6

costs[“b”] = 2

costs[“fin”] = infinity

还需要一个存储父节点的散列表：

创建这个散列表的代码如下：

parents = {}

parents[“a”] = “start”

parents[“b”] = “start”

parents[“fin”] = None

最后，你需要一个数组，用于记录处理过的节点，因为对于同一个节点，你不用处理多次。

processed = []

准备工作做好了，下面来看看算法。

我先列出代码，然后再详细介绍。代码如下。

这就是实现狄克斯特拉算法的Python代码！函数find_lowest_cost_node的代码稍后列

出，我们先来看看这些代码的执行过程。

找出开销最低的节点。

获取该节点的开销和邻居。

遍历邻居。

每个节点都有开销。开销指的是从起点前往该节点需要多长时间。在这里，你计算从起点出发，经节点B前往节点A（而不是直接前往节点A）需要多长时间。

接下来对新旧开销进行比较。

找到了一条前往节点A的更短路径！因此更新节点A的开销。

这条新路径经由节点B，因此节点A的父节点改为节点B。

现在回到了for循环开头。下一个邻居是终点节点。

经节点B前往终点需要多长时间呢？

需要7分钟。终点原来的开销为无穷大，比7分钟长。

设置终点节点的开销和父节点。

你更新了节点B的所有邻居的开销。现在，将节点B标记为处理过。

找出接下来要处理的节点。

获取节点A的开销和邻居。

节点A只有一个邻居：终点节点。

当前，前往终点需要7分钟。如果经节点A前往终点，需要多长时间呢？

经节点A前往终点所需的时间更短！因此更新终点的开销和父节点。

处理所有的节点后，这个算法就结束了。希望前面对执行过程的详细介绍让你对这个算法有更深入的认识。函数find_lowest_cost_node找出开销最低的节点，其代码非常简单，如下所示。

完整代码如下：