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*算法了。
来源:首一标准型