python算法4.11

#python算法4.11| 来源: 网络整理| 查看: 265

特点：

单源最短路径算法，得到所有点的最短路径树

dijkstra为由路径树优化，得到最短路径树的搜索过程，这一过程的主要原则是最短枝优先，即搜索当前点到邻接点的最短节点（因此被认为是基于贪心策略）。基于这一原则可得到全局最短路径

基本步骤：一）初始化

以图为基础，建立最短路径集合set，为搜索点集合unsearch，当前搜索节点point，通过set的最短路径到所有点的距离dis，确定或估计的最短路径path（dis、path分两部分，一部分为set点的已经确定的实际最短距离，另一部分为unsearch中的估计的最短距离）

二）点遍历、距离更新

从dis中选择估计最短距离中最短的点，其估计最短距离被确认为实际最短距离，将点放入set中，点更新为point

根据point及源点到point的最短距离，更新其余估计最短距离，如果距离被更新，更新path为当前点加当前点path

重复步骤二），直到所有点被搜索完毕，加入到set中

结果：

dis中即为源点到各点的最短距离，及最短路径，据此可以确定最短路径树

注意点：为什么迪杰斯特拉算法不能有负权重边？

算法根据point到unsearch中的估计最短距离的最小值确定实际最短距离，这个过程需要非负边保证，如下图，当1点为point时，当有非边时，不能保证9+x>7，无法确认7为实际最短距离，算法不一定可行

例题：

王朗欲与孔明试比高，王朗与军师较量心切，想从曹营（5）找到到达蜀地（1）用时最短的路线，我有一计（dijkstra），请静听

一）

初始化

Set（5）

Unsearch（4、6、3、2、1）

Point（5）

Dis及path

二）

Set（5、4）

Unsearch（6、3、2、1）

Point（4）

Dis及path

5、4

三）

Set（5、4、6）

Unsearch（3、2、1）

Point（6）

Dis及path

5、6

5、4

5、6

四）

Set（5、4、6、3）

Unsearch（2、1）

Point（3）

Dis及path

5、6

5、4

5、6、3

五）

Set（5、4、6、3、1）

Unsearch（1）

Point（1）

Dis及path

5、6

5、4

5、6、3

结果：

Set（5、4、6、3、1、2）

Unsearch（）

5、6

5、4

5、6、3

经过上所述算法，可以得到所有点到源点的最短路径，但是王朗又要求使用python实现，我从未见过如此厚颜无耻之人（滑稽）

代码：

（代码中使用a、b、c、d、e、f代替点1、2、3、4、5、6；如果邻接表正确，此代码对有向图应该也是可行的，如有问题，还请指正）

# -*- coding: utf-8 -*- # @Time : 2019/4/11 # @Author : Zhao huilin # @FileName: dijkstra.py # @Software: PyCharm # @Blog ：https://me.csdn.net/nominior import numpy as np graph_chain = { 'a': {'b': 7, 'c': 9, 'f': 14}, 'b': {'a': 7, 'c': 10, 'd': 15}, 'c': {'a': 9, 'b': 10, 'd': 11, 'f': 2}, 'd': {'b': 15,'c': 11, 'e': 6}, 'e': {'d': 6, 'f': 9}, 'f': {'a': 14, 'c': 2, 'e': 9} } # 这里矩阵未传入graph中使用，而是在graph使用链表生成，也可以传入矩阵和及按顺序的点列表 # 但矩阵在后续处理中是必须的，应为此代码后续处理基于矩阵进行权重查找 graph_matrix = [[0.0, 7.0, 9.0, np.inf, np.inf, 14.0], [7.0, 0.0, 10.0, 15.0, np.inf, np.inf], [9.0, 10.0, 0.0, 11.0, np.inf, 2.0], [np.inf, 15.0, 11.0, 0.0, 6.0, np.inf], [np.inf, np.inf, np.inf, 6.0, 0.0, 9.0], [14.0, np.inf, 2.0, np.inf, 9.0, 0.0]] class graph(): def __init__(self,vertexs=None,chain=None,matrix=None): self.vertexs = vertexs self.chain = chain self.matrix = matrix if vertexs is None and chain is not None: self.vertexs = list(chain.keys()) if matrix is None and chain is not None: self.matrix = self.chain_matrix() def __str__(self): return str(self.chain) def chain_matrix(self): matrix = np.zeros((len(self.vertexs), len(self.vertexs))) matrix += np.inf keys = list(self.chain.keys()) for key, value in self.chain.items(): key_index = self.vertexs.index(key) for k, v in value.items(): k_index = self.vertexs.index(k) matrix[key_index][k_index] = v matrix[key_index][key_index] = 0 return matrix.tolist() class dijkstra_path(): def __init__(self,graph,src_vertex): self.graph = graph self.src_vertex = src_vertex self.set = self.get_set() self.unsearch = self.get_unsearch() self.dis = self.get_dis() self.path = self.get_path() self.point = self.get_point() def get_set(self): return [self.src_vertex] def get_unsearch(self): unsearch = self.graph.vertexs[:] unsearch.remove(self.src_vertex) return unsearch def get_dis(self): dis = {} vertexs = self.graph.vertexs index = vertexs.index(self.src_vertex) for i,distance in enumerate(self.graph.matrix[index]): dis[vertexs[i]] = distance return dis def get_path(self): path = {} vertexs = self.graph.vertexs index = vertexs.index(self.src_vertex) for i,distance in enumerate(self.graph.matrix[index]): path[vertexs[i]] = [] if distance != np.inf: path[vertexs[i]].append(self.src_vertex) return path def get_point(self): return self.src_vertex # 首先根据dis、index及set(若出现权重相等)确定下一个路径点 def update_point(self,index): dis_sort = list(self.dis.values()) dis_sort.sort() point_dis = dis_sort[index] for key,distance in self.dis.items(): if distance == point_dis and key not in self.set: self.point = key break # 路径、距离更新，原距离>point距离+point到各点距离，则更新 def update_dis_path(self): new_dis = {} index_point = self.graph.vertexs.index(self.point) for i,key in enumerate(self.dis.keys()): new_dis[key] = self.dis[self.point] + self.graph.matrix[index_point][i] if new_dis[key]

【本文地址】

公司简介

联系我们