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

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

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

首先，必须要清楚的是，Dijkstra算法是一种贪心算法，因此，它无法处理有负权边的图（总之就是这么个原理）。

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

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

am = [None,
      [None, 0, 3, 1, 0, 0, 0],
      [None, 0, 0, 0, 3, 0, 0],
      [None, 0, 1, 0, 0, 2, 0],
      [None, 0, 0, 0, 0, 0, 4],
      [None, 0, 0, 0, 1, 0, 0],
      [None, 0, 0, 0, 0, 5, 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列表中已被访问过：

if visited[index]:                                           # 判断是否访问过
    return

Dijkstra算法是一种贪心算法（我们在开始是提过），它在向下进行递归的时候会选择距当前节点的最短距离⁴因此，我们还需要在函数内部定义一个用于存储它到它的邻接节点的距离的列表：

dis_of_index = [inf, inf, inf, inf, inf, inf, inf]           # 用于存储它到它的邻接节点的距离，索引表示它是哪一个节点

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

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

现在，我们终于迎来了最重要的部分——Dijkstra算法的核心。
Dijkstra算法是一个贪心算法，它需要知道起始点距每一个节点的长度（列表dis）和离当前节点最近的节点的长度（列表dis_of_index）。
开始时，Dijkstra算法会遍历当前节点的所有节点：

这时，它发现，“1”的邻接节点有“2”、“3”，并且，“1”到“2”的聚利时3，“1”到“3”的距离是2。程序把这些距离存在了列表dis_of_index中，程序发现，“1”是起始点，在我们最开始，距离列表dis除起始点外的每一项都是无穷大。现在，“1”到“2”距离3，而从起始点到“1”的距离是0，程序把两个数相加，这表示起始点到“2”的距离，它发现，新的走法到“2”的长度3小于原来列表中到“2”的长度无穷大，因此它更新了列表dis的第2项，使它变为3。以此类推，我们又更改了dis的第3项。
然后，程序会进行递归，它选择了距当前节点“1”距离最短的节点“3”作为下一个节点。
这就完了？不！还没完！
我们写Dijkstra算法的最终目的是为了寻找从起始点到某一点的最短路径，所以，我们要通过某种方法把路径存储下来。这里，我们通过一个字典，它的key代表它是哪一个节点，value代表起始点到它的最短路径。因为我要把后面遍历到了那一节点的值添加到当前节点的到起始点的最短路径上，因此，我要把字典初始化成：

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

当我们以这种方法找最短路径时，最后，我们发现节点“6”的最短路径长度是9而不是预计的8，这是因为，在遍历到“5”的时候，我们发现“4”的最短路径长度更改了（不信你就试试）但我们最初到达“6”要经过“4”，导致“6”的最短路径长度没有及时更新，出现了错误的结果。这样，在更新了最短路径时，我们要把这个节点的访问状态标记为“未访问”，这样，才可以得到正确的结果。

def dijkstra(index: int):                                        # 进行Dijkstra算法
    if visited[index]:                                           # 判断是否访问过
        return
    dis_of_index = [inf, inf, inf, inf, inf, inf, inf]           # 用于存储它到它的邻接节点的距离，索引表示它是哪一个节点
    visited[index] = 1                                           # 标记已访问
    for i in range(1, 7):
        if am[index][i]:
            if dis[index] + am[index][i] < dis[i]:
                dis[i] = dis[index] + am[index][i]
                visited[i] = 0
                dic[i] = dic[index] + '->' + str(i)
            dis_of_index[i] = am[index][i]
    next_index = dis_of_index.index(min(dis_of_index))
    dijkstra(next_index)

am = [None,
      [None, 0, 3, 1, 0, 0, 0],
      [None, 0, 0, 0, 3, 0, 0],
      [None, 0, 1, 0, 0, 2, 0],
      [None, 0, 0, 0, 0, 0, 4],
      [None, 0, 0, 0, 1, 0, 0],
      [None, 0, 0, 0, 0, 5, 0]
      ]
inf = float("inf")                                               # 表示无穷大
dis = [inf, 0, inf, inf, inf, inf, inf]                          # 用于把每一个节点到起始点的距离存储下来，索引表示它是哪一个节点
visited = [None, 0, 0, 0, 0, 0, 0]                               # 访问列表，0表示未访问，1表示已访问，索引表示它是哪一个节点
dic = {1: '1', 2: '2', 3: '3', 4: '4', 5: '5', 6: '6'}           # 记录最短路径


def dijkstra(index: int):                                        # 进行Dijkstra算法
    if visited[index]:                                           # 判断是否访问过
        return
    dis_of_index = [inf, inf, inf, inf, inf, inf, inf]           # 用于存储它到它的邻接节点的距离，索引表示它是哪一个节点
    visited[index] = 1                                           # 标记已访问
    for i in range(1, 7):
        if am[index][i]:
            if dis[index] + am[index][i] < dis[i]:
                dis[i] = dis[index] + am[index][i]
                visited[i] = 0
                dic[i] = dic[index] + '->' + str(i)
            dis_of_index[i] = am[index][i]
    next_index = dis_of_index.index(min(dis_of_index))
    dijkstra(next_index)