- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章python3实现Dijkstra算法最短路径的实现由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
现有一个有向赋权图。如下图所示:
问题:根据每条边的权值,求出从起点s到其他每个顶点的最短路径和最短路径的长度。 说明:不考虑权值为负的情况,否则会出现负值圈问题。 s:起点 v:算法当前分析处理的顶点 w:与v邻接的顶点 d v d_v dv:从s到v的距离 d w d_w dw:从s到w的距离 c v , w c_{v,w} cv,w:顶点v到顶点w的边的权值 。
Dijkstra算法按阶段进行,同无权最短路径算法(先对距离为0的顶点处理,再对距离为1的顶点处理,以此类推)一样,都是先找距离最小的。 在每个阶段,Dijkstra算法选择一个顶点v,它在所有unknown顶点中具有最小的 d v d_v dv,同时算法声明从s到v的最短路径是known的。阶段的其余部分为,对w的 d v d_v dv(距离)和 p v p_v pv(上一个顶点)更新工作(当然也可能不更新)。 在算法的每个阶段,都是这样处理的: 【0.5】在无权的情况下,若 d w d_w dw= ∞ \infty ∞则置 d w = d v + 1 d_w=d_v+1 dw=dv+1(无权最短路径) 【1】在有权的情况下,若 d w d_w dw= ∞ \infty ∞则置 d w = d v + c v , w d_w=d_v+c_{v,w} dw=dv+cv,w 【2】若 d w d_w dw!= ∞ \infty ∞,开始分析:从顶点v到顶点w的路径,若能使得w的路径长比w原来的路径长短一点,那么就需要对w进行更新,否则不对w更新。即满足 d v + c v , w < d w d_v+c_{v,w} 。
考虑Dijkstra算法过程中,有一个数据变化表.
初始状态如上。开始顶点s是 v 1 v_1 v1,所有顶点都是unknown的。 v 1 v_1 v1的 d v d_v dv的值为0,因为它是起点.
【1】选择unknown顶点中, d v d_v dv值最小的顶点,即顶点 v 1 v_1 v1。首先将 v 1 v_1 v1标记为known。对与 v 1 v_1 v1邻接的顶点 v 2 v 4 v_2 v_4 v2v4进行调整: v 2 v_2 v2的距离变为 d v + c v , w d_v+c_{v,w} dv+cv,w即 v 1 v_1 v1的 d v d_v dv值+ c 1 , 2 c_{1,2} c1,2即0+2=2, v 2 v_2 v2的 p v p_v pv值变为 v 1 v_1 v1;同理,对 v 4 v_4 v4作相应的处理.
【2】选择unknown顶点中, d v d_v dv值最小的顶点,即顶点 v 4 v_4 v4(其距离为1,最小)。将 v 4 v_4 v4标记为known。对其邻接的顶点 v 3 v 5 v 6 v 7 v_3 v_5 v_6 v_7 v3v5v6v7作相应的处理.
【3】选择unknown顶点中, d v d_v dv值最小的顶点,即顶点 v 2 v_2 v2(其距离为2,最小)。将 v 2 v_2 v2标记为known。对其邻接的顶点 v 4 v 5 v_4v_5 v4v5作相应的处理。但 v 4 v_4 v4是已知的,所以不需要调整;因为经过 v 2 v_2 v2到 v 5 v_5 v5的距离为2+10=12,而s到 v 5 v_5 v5路径为3是已知的(上表中, v 5 v_5 v5的 d v d_v dv为3),12>3,所以也不需要也没有必要调整.
【4】选择unknown顶点中, d v d_v dv值最小的顶点,即顶点 v 5 v_5 v5(距离为3,最小,其实还有 v 3 v_3 v3也是距离为3,但博主发现这里,先 v 5 v_5 v5再 v 3 v_3 v3和先 v 3 v_3 v3再 v 5 v_5 v5的运行结果都是一样的)。将 v 5 v_5 v5标记为known。对其邻接的顶点 v 7 v_7 v7作相应的处理。但原路径长更小,所以不用调整.
【5】再对 v 3 v_3 v3处理。对 v 6 v_6 v6的距离下调到3+5=8 。
【6】再对 v 7 v_7 v7处理。对 v 6 v_6 v6的距离下调到5+1=6 。
【7】最后,再对 v 6 v_6 v6处理。不需调整.
上述实现过程对应的算法,可能需要用到优先队列,每次出队 d v d_v dv值最小的顶点,因为如果只是遍历来找到 d v d_v dv值最小的顶点,可能会花费很多时间.
数据变化表的最终情况如下:
现在我们能找到起点 v 1 v_1 v1到任意的 v i v_i vi(除了起点)的最短路径,及其最短路径长。 比如,找到 v 1 v_1 v1到 v 3 v_3 v3的最短路径。 【1】 v 3 v_3 v3的 d v d_v dv值为3,所以最短路径长为3 【2】 v 3 v_3 v3的 p v p_v pv值为 v 4 v_4 v4,所以 v 3 v_3 v3的上一个顶点为 v 4 v_4 v4 【3】到代表 v 4 v_4 v4的第四行,发现 v 4 v_4 v4的 p v p_v pv值为 v 1 v_1 v1,所以 v 4 v_4 v4的上一个顶点为 v 1 v_1 v1 【4】 v 1 v_1 v1是起点,结束。 v 3 v_3 v3上一个是 v 4 v_4 v4, v 4 v_4 v4上一个是 v 1 v_1 v1,反过来就得到了最短路径 v 1 = > v 4 = > v 3 v_1=>v_4=>v_3 v1=>v4=>v3 上述分析,其实就是求最短路径的算法的思想:在对每个顶点对象进行处理后变成数据变化表的最终情况后,可以通过对任意顶点 v i v_i vi的 p v p_v pv值,回溯得到反转的最短路径.
纸上得来终觉浅,绝知此事要躬行!使用python3来实现功能。 本文提到,将使用优先队列来实现寻找未知顶点中,具有最小dist的顶点。使用python已有实现好的优先队列。但实验中报错如下:
意思,Vertex实例并不支持小于比较运算符。所以需要实现Vertex类的__lt__方法。下面科普一下:
。
方法名 | 比较运算符 | 含义 |
---|---|---|
__eq__ |
== | equal |
__lt__ |
< | less than |
__le__ |
<= | less and equal |
__gt__ |
> | greater than |
__ge__ |
>= | greater and equal |
。
但很遗憾,python库自带的优先队列from queue import PriorityQueue,并不满足本文的需求。当PriorityQueue的元素为对象时,需要该对象的class实现__lt__函数,在往优先队列里添加元素时,内部是用的堆排序,堆排序的特点为每个堆(以及每个子堆)的第一个元素总是那个最小的元素。关键在于,在建立了这个堆后,堆就已经记录下来了创建堆时各个元素的大小关系了,在创建优先队列后,再改变某个对象的值,这个堆的结构是肯定不会变的,所以这种堆排序造成了排序是一次性的,如果之后某个对象的属性发生变化,堆的结构也不会随之而改变.
或者说,我们想要的优先队列肯定不是系统提供的优先队列,因为我们要支持可变对象的成员修改导致堆的改变,解决方案有三种,1.内部使用的堆排序的堆,最起码要支持,删除任意节点和增加节点操作(因为这两步就可以达到修改的效果了)2.这个内部堆,在执行出队操作时,考察哪个节点有修改操作,再把堆改变到正确的形态,再出队3.维护一个list,进行排降序,然后每改变一个可变对象的值,就对这个对象进行冒泡或者二分查找找到位置(因为别的都是已经排好序的了,只有它不在正确的位置),最后再list.pop(),但第三个方案是我后来想到的,所以下面代码并不是这样实现的,读者可以进行尝试,肯定比每次遍历全部快.
应该说,可能用不上队列了。我们可能只需要一个list或者set来存储v,在出队前随便vi改变其dist,在出队时再遍历找到最小的dist的vi,再删除掉这个vi即可。因为vi的dist一直在变,需求特殊,但是没必要专门造个轮子(感觉这个轮子也不好造),虽然时间复杂度可能高了点,但代码简单了啊.
失效代码如下:三个节点对象的dist都是无穷大,在三个对象都进入队列,再把v3的dist改成0,想要的效果是出队出v3,但出队出的是v1。原因如上:
from queue import PriorityQueue class Vertex: #顶点类 def __init__(self,vid,dist): self.vid = vid self.dist = dist def __lt__(self,other): return self.dist
而如果将在入队前,就把dist改变了,就能正确的出队.
v3.dist = 0 for i in range(0,len(vlist)): q.put(vlist[i]) #结果为vid: 3
class Vertex: #顶点类 def __init__(self,vid,outList): self.vid = vid#出边 self.outList = outList#出边指向的顶点id的列表,也可以理解为邻接表 self.know = False#默认为假 self.dist = float('inf')#s到该点的距离,默认为无穷大 self.prev = 0#上一个顶点的id,默认为0 def __eq__(self, other): if isinstance(other, self.__class__): return self.vid == other.vid else: return False def __hash__(self): return hash(self.vid) #创建顶点对象 v1=Vertex(1,[2,4]) v2=Vertex(2,[4,5]) v3=Vertex(3,[1,6]) v4=Vertex(4,[3,5,6,7]) v5=Vertex(5,[7]) v6=Vertex(6,[]) v7=Vertex(7,[6]) #存储边的权值 edges = dict() def add_edge(front,back,value): edges[(front,back)]=value add_edge(1,2,2) add_edge(1,4,1) add_edge(3,1,4) add_edge(4,3,2) add_edge(2,4,3) add_edge(2,5,10) add_edge(4,5,2) add_edge(3,6,5) add_edge(4,6,8) add_edge(4,7,4) add_edge(7,6,1) add_edge(5,7,6) #创建一个长度为8的数组,来存储顶点,0索引元素不存 vlist = [False,v1,v2,v3,v4,v5,v6,v7] #使用set代替优先队列,选择set主要是因为set有方便的remove方法 vset = set([v1,v2,v3,v4,v5,v6,v7]) def get_unknown_min():#此函数则代替优先队列的出队操作 the_min = 0 the_index = 0 j = 0 for i in range(1,len(vlist)): if(vlist[i].know is True): continue else: if(j==0): the_min = vlist[i].dist the_index = i else: if(vlist[i].dist
运行结果与数据变化表的最终情况一致.
把以下代码和以上代码合起来就可以运行成功,使用递归的思想来做:
def real_get_traj(start,index): traj_list = [] def get_traj(index):#参数是顶点在vlist中的索引 if(index == start):#终点 traj_list.append(index) print(traj_list[::-1])#反转list return if(vlist[index].dist == float('inf')): print('从起点到该顶点根本没有路径') return traj_list.append(index) get_traj(vlist[index].prev) get_traj(index) print('该最短路径的长度为',vlist[index].dist) real_get_traj(1,3) real_get_traj(1,6)
如图所示,从v1到v3的最短路径为:[1, 4, 3] 从v1到v6的最短路径为:[1, 4, 7, 6] 。
Dijkstra算法要求边上的权值不能为负数,不然就会出错。如上,本来最短路径是012,但由于算法是贪心的,所以只会直接选择到2 。
注意,只有有向无圈图才有拓扑排序.
如果知道图是无圈图,那么我们可以通过改变声明顶点为known的顺序(原本这个顺序是,每次从unknown里面找出个最小dist的顶点),或者叫做顶点选取法则,来改进Dijkstra算法。新法则以拓扑排序选择顶点。由于选择和更新(每次选择和更新完成后,就会变成数据变化表中的某一种情况)可以在拓扑排序执行的时候进行,因此算法能一趟完成.
因为当一个顶点v被选取以后,按照拓扑排序的法则它肯定没有任何unknown顶点到v(指明方向)的入边,因为v的距离 d v d_v dv不可能再下降了(因为根本没有别的路到v了),所以这种选择方法是可行的.
使用这种方法不需要优先队列.
到此这篇关于python3实现Dijkstra算法最短路径的实现的文章就介绍到这了,更多相关python3 最短路径内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我! 。
原文链接:https://blog.csdn.net/anlian523/article/details/80893372 。
最后此篇关于python3实现Dijkstra算法最短路径的实现的文章就讲到这里了,如果你想了解更多关于python3实现Dijkstra算法最短路径的实现的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
谁能告诉我这个 Dijkstra 算法中优先级队列的空间复杂度。请注意,这里可以将一个顶点添加到队列中不止一次。但是,由于访问集,它不会被处理超过一次。这就是为什么我想知道队列的最大大小可以达到的原因
为什么我们不能将 Dijkstra 算法应用于具有负权重的图? 最佳答案 如果每次从 C 到 D 旅行都得到报酬,那么找到从 A 到 B 的最便宜的路径意味着什么? 如果两个节点之间存在负权重,则“最
我正在阅读 工作中的程序员 . 我在 Donald Knuth 的采访中看到了这一段。 Seibel: It seems a lot of the people I’ve talked to had
我一整天都在努力理解 Dijkstra 算法并实现,但没有取得任何重大成果。我有一个城市及其距离的矩阵。我想做的是给定一个起点和一个终点,找到城市之间的最短路径。 示例: __0__ __1
这个问题不太可能帮助任何 future 的访问者;它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况有关,这些情况并不普遍适用于互联网的全局受众。为了帮助使这个问题更广泛地适用,visit
一 问题描述 小明为位置1,求他到其他各顶点的距离。 二 实现 package graph.dijkstra; import java.util.Scanner; import java.util.
一 问题背景 在现实生活中,很多问题都可以转化为图来解决问题。例如,计算地图中两点之间的最短距离、网络最小成本布线,以及工程进度控制,等等。这些问题都涉及最小路径的求解。 二 Dijkstra 算法
谁能告诉我这个程序的错误在哪里,这真的很有帮助,我尽力解决了这个问题,这段代码只通过了两个测试用例给定一个无向图和一个起始节点,确定从起始节点到图中所有其他节点的最短路径的长度。如果一个节点不可到达,
除了 Dijkstra 之外,还有其他方法可以计算接近完整图的最短路径吗?我有大约 8,000 个节点和大约 1800 万条边。我已经完成了线程 "a to b on map"并决定使用 Dijkst
我知道 Dijkstra 的算法、Floyd-Warshall 算法和 Bellman-Ford 算法,用于查找图中 2 个顶点之间的最便宜路径。 但是当所有边的成本都相同时,最便宜的路径是边数最少的
我的问题如下:根据不同的消息来源,Dijkstra 算法只不过是 Uniform Cost Search 的一种变体。我们知道 Dijkstra 的算法会找到源和所有目的地(单源)之间的最短路径。但是
所以我的问题是我有一个带有 的有向图 G非负 边长度,我希望找到两个节点 u 和 v 之间的最短路径,以便它们只通过图中的一个标记节点。 如果我们没有涉及标记节点的条件,这个问题可以使用 Dijkst
对于使用最小堆优先级队列的 Dijkstra 实现,我将其设置为查找网络上不存在的站,以便它必须检查所有内容。我的问题是由于整体时间复杂度 O(V + E log V) ,为什么网络查找到一个站点的最
我试图找出是否可以使用 Dijkstra 算法来找到有向无环路径中的最长路径。我知道由于负成本循环,不可能在一般图中找到 Dijkstra 的最长路径。但我认为它应该在 DAG 中工作。通过谷歌我发现
我正在研究 Dijkstra 算法,我真的需要找到所有可能的最短路径,而不仅仅是一条。我正在使用邻接矩阵并应用 Dijkstra 算法,我可以找到最短路径。但是我需要以最低成本找到所有路径,我的意思是
我正在尝试创建 Dijkstra 寻路的实现,除了我要求它创建一条在同一位置开始和结束的路线之外,它似乎工作得很好。 JSFiddle:http://jsfiddle.net/Lt6b4ecr/ 我需
我们可以使用负权重的 Dijkstra 算法吗? 停止! 在您认为“大声笑,您可以在两点之间无休止地跳跃并获得无限便宜的路径”之前,我更多地考虑的是单向路径。 对此的应用程序将是一个带有点的山地地形。
我认为 Dijkstra 算法是确定的,因此,如果您选择相同的起始顶点,您将得到相同的结果(到每个其他顶点的距离相同)。但我不认为它是确定性的(它为每个操作定义了以下操作),因为这意味着它不必首先搜索
我找到了this code使用 Dijkstra 算法来查找加权图中两个节点之间的最短路径。我看到的是代码没有跟踪访问过的节点。但是它对于我尝试过的所有输入都适用。我添加了一行代码来跟踪访问过的节点。
我将 Dijkstra 算法 的 C++ 实现转换为 Java。当我运行 Java 代码时,我没有得到预期的输出 我的 C++ 代码的预期: Minimum distance for source v
我是一名优秀的程序员,十分优秀!