迪杰斯塔拉（Dijkstra）算法求最短路径

序关于DijkstraDijkstra算法讲解Dijkstra算法的弊端第一步：进行初始化第二步：主程序开始又是初始化核心的核心[^5]最开始出口 终于出现的主程序代码 完整的代码

序

本文作者在学习Dijkstra算法时，发现参考书与CSDN其他博客上语言类似火星文或天书，最后，作者靠着他惊人的数学天赋总算弄懂了其原理。作者对此现象深感不平，因此，我写了一个公益性的博文，以让被火星文搞得不知所措的程序员或未来的程序员们深深的理解Dijkstra算法的奥秘。

关于Dijkstra

艾兹格·W·迪科斯彻 （Edsger Wybe Dijkstra，1930年5月11日~2002年8月6日），生于荷兰Rotterdam， 计算机科学家，毕业就职于荷兰莱顿大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获得过1974年AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。

——选自《百度百科：艾兹格·迪科斯彻》

Dijkstra^1：

Dijkstra算法讲解

Dijkstra算法的弊端

首先，必须要清楚的是，Dijkstra算法是一种贪心算法，因此，它无法处理有负权边的图。这是因为当杜仲存在负权边时，一个未访问过的定点则有可能经由某个负权路径回流到已经访问的节点上，进而Dijkstra算法会陷入无限循环中，因此，一般的Dijkstra算法无法应用于负权图。

第一步：进行初始化

首先，我们先简单的画一个用于测试的图^2：

那么，让我们先用邻接矩阵来表示它：

am = [None,[None, inf, 3, 1, inf, inf, inf],[None, inf, inf, inf, 3, inf, inf],[None, inf, 1, inf, inf, 2, inf],[None, inf, inf, inf, inf, inf, 4],[None, inf, inf, inf, 1, inf, inf],[None, inf, inf, inf, inf, 5, inf]]

之所以我们把与它无关联的节点标记为“inf”是因为“0”应该表示与它距离为0的节点（也就是它自己）

Dijkstra算法中，我们需要一个用于记录从起始点到每一个节点的最短路径的长度的列表：

inf = float("inf") # 表示无穷大dis = [inf, 0, inf, inf, inf, inf, inf]# 用于把每一个节点到起始点的距离存储下来，索引表示它是哪一个节点

之后，我们需要一个在图算法中无处不在的表示节点访问状态的列表——visited：

visited = [None, 0, 0, 0, 0, 0, 0] # 访问列表，0表示未访问，1表示已访问，索引表示它是哪一个节点

至此，第一步完成³

第二步：主程序开始

又是初始化

额，首先，我们要养成良好的习惯：

def dijkstra(index: int):# 进行Dijkstra算法pass

另外，在进行递归的时候，为了防止出现死循环，还需要对visited列表进行更改，是当前节点被标记为已访问^4：

visited[index] = 1 # 标记已访问

核心的核心⁵

最开始

现在，我们终于迎来了最重要的部分——Dijkstra算法的核心。

Dijkstra算法是一个贪心算法，它需要知道起始点距每一个节点的长度（列表dis）和离初始节点最近的节点的距离。

开始时，Dijkstra算法会遍历当前节点的所有节点：

这时，它发现，“1”是起始点，在我们最开始，距离列表dis除起始点外的每一项都是无穷大。现在，“1”到“2”距离3，而从起始点到“1”的距离是0，程序把两个数相加，这表示起始点到“2”的距离，它发现，新的走法到“2”的长度3小于原来列表中到“2”的长度无穷大，因此它更新了列表dis的第2项，使它变为3。以此类推，我们又更改了dis的第3项。

然后，程序会进行递归，它选择了距起始节点“1”距离最短的节点“3”作为下一个节点。

这就完了？不！还没完！

我们写Dijkstra算法的最终目的是为了寻找从起始点到某一点的最短路径，所以，我们要通过某种方法把路径存储下来。这里，我们通过一个字典，它的key代表它是哪一个节点，value代表起始点到它的最短路径。因为我要把后面遍历到了那一节点的值添加到当前节点的到起始点的最短路径上，因此，我要把字典初始化成^6：

dic = {1: '1', 2: '', 3: '', 4: '', 5: '', 6: ''} # 记录最短路径

出口

这时，一些眼尖的人发现了：这个程序没有出口！

不急。通过我的讲解，我们知道，下一次进行递归的节点是距起始节点最近、且未被访问过的节点。这里，我们先找出符合要求的节点，当程序找不出符合要求的节点时，就表示，所有节点都被访问过了。这就是一个出口。

终于出现的主程序代码

def dijkstra(index: int):# 进行Dijkstra算法visited[index] = 1 # 标记已访问for i in range(1, 7):if dis[index] + am[index][i] < dis[i]:dis[i] = dis[index] + am[index][i]dic[i] = dic[index] + '->' + str(i)_min = infnext_index = 0for i in range(1, len(dis)):if dis[i] <= _min and not visited[i]:_min = dis[i]next_index = iif next_index == 0: # 判断是否访问过，因为当visited中除第0项”None“return # 以外其他的元素都为1时，next_index不会被更改dijkstra(next_index)

完整的代码

inf = float("inf") # 表示无穷大am = [None,[None, inf, 3, 1, inf, inf, inf],[None, inf, inf, inf, 3, inf, inf],[None, inf, 1, inf, inf, 2, inf],[None, inf, inf, inf, inf, inf, 4],[None, inf, inf, inf, 1, inf, inf],[None, inf, inf, inf, inf, 5, inf]]dis = [inf, 0, inf, inf, inf, inf, inf]# 用于把每一个节点到起始点的距离存储下来，索引表示它是哪一个节点visited = [None, 0, 0, 0, 0, 0, 0] # 访问列表，0表示未访问，1表示已访问，索引表示它是哪一个节点dic = {1: '1', 2: '', 3: '', 4: '', 5: '', 6: ''} # 记录最短路径def dijkstra(index: int):# 进行Dijkstra算法visited[index] = 1 # 标记已访问for i in range(1, 7):if dis[index] + am[index][i] < dis[i]:dis[i] = dis[index] + am[index][i]dic[i] = dic[index] + '->' + str(i)_min = infnext_index = 0for i in range(1, len(dis)):if dis[i] <= _min and not visited[i]:_min = dis[i]next_index = iif next_index == 0: # 判断是否访问过，因为当visited中除第0项”None“return # 以外其他的元素都为1时，next_index不会被更改dijkstra(next_index)

来源：百度百科 ↩︎

来源：noi.vip——工信部 Python 6级-NOI算法 李做成博士 课时十 图上的路径II（之后的几张类似风格的图片是经过我处理后的，底片还是这一张图片） ↩︎

其实还有一个字典需要使用，但为了讲解方便，我们在核心的核心这一节中会提到它 ↩︎

这一部分的具体内容我们会在下文详细介绍 ↩︎

为了使读者深刻理解Dijkstra算法的核心，本节中没有大篇幅的代码 ↩︎

这就是注释3所提到的字典 ↩︎