最短路径算法之Dijkstra(迪杰斯特拉)

太过爱你忘了你带给我的痛 2023-06-25 04:51 100阅读 0赞

# Dijkstra算法 #

迪杰斯特拉(Dijkstra)是典型的最短路径算法，顾名思义就是从一个点出发，到达另一个点的最短路径。

# 算法原理 #

例如，我们以一个案例来讲解他的算法原理。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]

**大体的思想是：每次选择一个未被访问过、并且最短距离最短的点作为访问顶点，然后访问各个顶点，让访问顶点作为新的路径，到各个顶点之间的最短距离与各个顶点原本的最短距离进行比较，发现距离更短则然后进行路径更新。**  
一、 首先，我们需要初始化几个必要的东西：

1.  dis = \[inf, inf, inf, inf, inf, inf, inf\] \# 记录出发顶点到其他各个顶点的最短累计距离，inf表示无穷大
2.  pre = \[-1, -1, -1, -1, -1, -1, -1\] \# 记录出发顶点到其他各个顶点的前驱顶
3.  visited = \[false, false, false, false, false, false, false\] \# 记录每个顶点是否已经访问过
4.  path = \[\[\], \[\], \[\], \[\], \[\], \[\], \[\]\] \# 记录出发顶点到其他各个顶点的最短路径

二、 A-G对应0-6。假如，我们要从G点出发，那么:  
dis = \[inf, inf, inf, inf, inf, inf, 0\]，其实就是G自己到自己的距离是0。visited = \[false, false, false, false, false, false, true\]；

三、 接下来，从G开始访问各个顶点，进行我们的第一步遍历更新了：  
我们以A为例子，原本到A点的最短距离为dis\[0\]，即为inf，那么如果是以G为访问顶点，G到A的最短距离应该就是G的最短距离+G与A间的距离即dis\[6\]+weight\[6\]\[0\]（weight是各个顶点之间的距离矩阵），发现从G到A的最短距离更短，那么就会进行更新：  
a. 更新A的最短距离，dis\[0\] = dis\[6\]+weight\[6\]\[0\] = 2  
b. 更新A的前驱顶点为G，pre\[0\] = 6；  
c. 更新A的最短路径，即更换为G的最短路径，然后加上自己，path\[0\] = path\[6\] + 0 = \[6, 0\]  
然后其他的点也是同理进行更新，最后的结果应该就是：  
dis = \[2, 3, inf, inf, 4, 6, 0\]  
pre = \[6, 6, -1, -1, 6, 6, -1\]  
path = \[\[6, 0\], \[6, 1\], \[\], \[\], \[6, 4\], \[6, 5\], \[\]\]

四、进行一轮更新之后，就需要更换访问顶点了。按照我们的思路：**选择一个未被访问过、并且最短距离最短的点作为访问顶点**。发现A的最短距离最短，那么就选择A为访问顶点，然后按照步骤三的方法再进行一轮更新；

五、 重复步骤三、四。我们总共有7个点，那么迭代6次就可以完成所有的更新了。

# 代码实现 #

import numpy as np
    
    
    class Graph:
    
        def __init__(self, vertex, weight):
            self.vertex = vertex
            self.weight = weight
    
            self.dis = None  # 记录出发顶点到其他各个顶点的最短累计距离
            self.pre = None  # 记录出发顶点到其他各个顶点的前驱顶点
            self.visited = None  # 记录每个顶点是否已经访问过
            self.path = None  # 记录出发顶点到其他各个顶点的最短路径
    
        def init(self, index):
            """ 初设化Dijkstra算法 :param index: 出发顶点 :return: """
            self.dis = np.full([len(self.vertex), ], np.inf)
            self.pre = [-1] * len(self.vertex)
            self.visited = [False] * len(self.vertex)
            self.path = [[] for i in range(len(self.vertex))]
    
            self.dis[index] = 0
            self.visited[index] = True
            self.path[index].append(self.vertex[index])
    
        def djs(self, index, show=True):
            """ Dijkstra算法的执行方法：以index为出发顶点，计算index达到其他各个顶点的最短距离 :param show: :param index: :return: """
            start_index = index
            self.init(index)
            self.update(index)
            for i in range(1, len(self.vertex)):
                index = self.update_vertex()
                self.update(index)
            if show:
                self.show_djs(start_index)
    
        def update(self, index):
            """ 以index为访问顶点，更新每个顶点的前驱顶点和累计距离 :param index: :return: """
            for i in range(len(self.vertex)):
                length = self.dis[index] + self.weight[index][i]
                # 当遇到能够能以更短距离达到自己的出发顶点时，则进行更新
                if (length < self.dis[i]) & (not self.visited[i]):
                    self.pre[i] = index  # 更换前驱节点
                    self.dis[i] = length  # 更换累计距离
                    # 更换路径
                    self.path[i] = self.path[index].copy()  # 前驱节点的最优路径
                    self.path[i].append(self.vertex[i])  # 再加上自己
    
        def update_vertex(self):
            """ 更新下次的访问顶点 :return: """
            dis = np.inf
            index = 0
            for i in range(len(self.vertex)):
                if (not self.visited[i]) & (dis > self.dis[i]):
                    dis = self.dis[i]
                    index = i
            self.visited[index] = True
            return index
    
        def show_djs(self, index):
            """ 打印Dijkstra算法的结果：出发顶点到各个顶点的最短距离和最优路径 :param index: :return: """
            for i in range(len(self.vertex)):
                if i == index:
                    continue
                print("{}到{}的最短距离为{}，最优路径为-->{}".format(
                    self.vertex[index], self.vertex[i], self.dis[i], self.path[i]))
    
    
    if __name__ == '__main__':
        vertex = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
        weight = [[np.inf, 5, 7, np.inf, np.inf, np.inf, 2],
                [5, np.inf, np.inf, 9, np.inf, np.inf, 3],
                [7, np.inf, np.inf, np.inf, 8, np.inf, np.inf],
                [np.inf, 9, np.inf, np.inf, np.inf, 4, np.inf],
                [np.inf, np.inf, 8, np.inf, np.inf, 5, 4],
                [np.inf, np.inf, np.inf, 4, 5, np.inf, 6],
                [2, 3, np.inf, np.inf, 4, 6, np.inf]]
        graph = Graph(vertex, weight)
        graph.djs(2)

欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430114814797.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191226070449574.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ==,size_16,color_FFFFFF,t_70
[20200430114814797.jpg]: https://img-blog.csdnimg.cn/20200430114814797.jpg