Dijkstra算法详解附完整python代码

1.定义

是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。

迪杰斯特拉算法主要特点是:从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。

算法核心部分的介绍在我另一篇文章也有提到:

(1条消息) A*算法详解及改进方法附核心python代码_首一标准型的博客-CSDN博客_a*算法的改进

2.问题描述

图1 所解决的路径图

如图1所示,节点1为初始节点,节点6为目标节点,根据这个图片,我们可以建立邻接表为:

g = {'1': {'2': 2, '3': 1, '4': 4},
     '2': {'4': 3, '6': 2},
     '3': {'5': 3},
     '4': {'6': 1},
     '5': {'4': 4, '6': 2}
     }

g是由图1有向加权图建立的邻接表,键为起始节点,值为指向的节点和他们之间的距离。

3.完整代码如下

class Dijkstra:
    def __init__(self, graph, goal):
        self.graph = graph
        self.goal = goal
        self.open_list = {}
        # open_list初始化为一个空字典,keys为节点'1''2'...,values为distance即从'1'到该点的实际代价
        self.closed_list = {}
        # closed_list初始化为一个空字典,键和值与open_list相同
        self.open_list['1'] = 0
        # 因为我们初始节点为'1',并且'1'到'1'的值为0,将其传入open_list列表中
        self.parent = {'1': None}
        # 初始父节点为字典型,初始键为'1'值为None,其中键是子节点,值是父节点
        self.min_dis = None
        # 初始最短路径长度为None

    def shortest_path(self):

        while True:
            if self.open_list is None:
                print('搜索失败, 结束!')
                break

            distance, min_node = min(zip(self.open_list.values(), self.open_list.keys()))  # 取出距离最小的节点
            self.open_list.pop(min_node)  # 将其从 open_list 中去除

            self.closed_list[min_node] = distance  # 将节点加入 closed_list 中

            if min_node == self.goal:  # 如果节点为终点
                self.min_dis = distance
                shortest_path = [self.goal]  # 记录从终点回溯的路径
                father_node = self.parent[self.goal]
                while father_node != '1':
                    shortest_path.append(father_node)
                    father_node = self.parent[father_node]
                shortest_path.append('1')
                print(shortest_path[::-1])  # 逆序
                print('最短路径的长度为:{}'.format(self.min_dis))
                print('找到最短路径, 结束!')
                return shortest_path[::-1], self.min_dis  # 返回最短路径和最短路径长度

            for node in self.graph[min_node].keys():  # 遍历当前节点的邻接节点
                if node not in self.closed_list.keys():  # 邻接节点不在 closed_list 中
                    if node in self.open_list.keys():  # 如果节点在 open_list 中
                        if self.graph[min_node][node] + distance < self.open_list[node]:
                            self.open_list[node] = distance + self.graph[min_node][node]  # 更新节点的值
                            self.parent[node] = min_node  # 更新继承关系
                    else:  # 如果节点不在 open_list 中
                        self.open_list[node] = distance + self.graph[min_node][node]
                        # 计算节点的值,并加入 open_list 中
                        self.parent[node] = min_node  # 更新继承关系


if __name__ == '__main__':
    g = {'1': {'2': 2, '3': 1, '4': 4},
         '2': {'4': 3, '6': 2},
         '3': {'5': 3},
         '4': {'6': 1},
         '5': {'4': 4, '6': 2}
         }
    goal = '6'
    dijk1 = Dijkstra(g, goal)
    dijk1.shortest_path()

我们设置起始节点为'1', 终点为'6',使用dijkstra算法找到的最短路径为:

['1', '2', '6']
最短路径的长度为:4

终点的设置可以改变,我们可以改变goal的值为'1','2','3','4','5','6'分别求出节点1到节点1,2,3,4,5,6的最短距离。在这个代码中我们默认设置起点为'1',想要修改可以通过 

self.open_list['1'] = 0

self.parent = {'1': None}

在class Dijkstra的初始函数中增加一个start起点的参数。

4.总结展望

其实增加start节点会变得和A*算法近似,因为Dijkstra主要是遍历所有的点,计算出各个点距离起点的最短距离,而A*算法是可以计算各个节点之间的距离,细心的朋友可以发现在判断最短距离时我们使用了这个代码

distance, min_node = min(zip(self.open_list.values(), self.open_list.keys()))  # 取出距离最小的节点

其中里面的distance就是g(n),即从起点到达当前点的代价

而A*算法考虑的是f(n)=g(n)+h(n)

h(n)是启发函数即从当前点到终点的距离,如何计算这个距离呢?

常见的三种启发函数有欧式距离,曼哈顿距离,对角线距离,但是都不适用于我们的问题,因为对于这个图难以设置各个点的坐标。对于更加规范的图我们可以稍微改进这个算法就是A*算法了。

来源:首一标准型

物联沃分享整理
物联沃-IOTWORD物联网 » Dijkstra算法详解附完整python代码

发表评论