易语言做购物网站,unity 做网站,网站做图尺寸,东风地区网站建设价格低目录
前言
Floyd弗洛伊德算法
定义
步骤
一、初始化
二、添加中间点
三、迭代
四、得出结果
时间复杂度
代码实现
结束语 前言
今天是坚持写博客的第18天#xff0c;希望可以继续坚持在写博客的路上走下去。我们今天来看看数据结构与算法当中的弗洛伊德算法。 Flo…目录
前言
Floyd弗洛伊德算法
定义
步骤
一、初始化
二、添加中间点
三、迭代
四、得出结果
时间复杂度
代码实现
结束语 前言
今天是坚持写博客的第18天希望可以继续坚持在写博客的路上走下去。我们今天来看看数据结构与算法当中的弗洛伊德算法。 Floyd弗洛伊德算法
定义
Floyd弗洛伊德算法是一种用于在加权图中找到所有顶点对之间的最短路径的算法。这个算法可以处理带有正权、负权甚至零权但不存在负权环路的图。
对于了解Floyd弗洛伊德算法我们需要先了解几个前置概念
加权图图中的每条边都有一个与之关联的权值最短路径从一个顶点到另一个顶点的总权值最小的路径负权环路一个环路即一条起点和终点相同的路径其所有边的权值之和为负。如果存在负权环路则最短路径问题可能没有解因为可以通过无限次地遍历这个环路来不断减小路径的总权值。 步骤
假设我们有如下的图 其中A到B的权值为2A到C的权值为6A到D的权值为5B到C的权值为1B到D的权值为4C到D的权值为3。我们可以先得出他的邻接矩阵 为什么对角线上的值都是零因为对角线上的路径都是一个环路图上没有自己指向自己的环路因此都是0。
下面进入正题如何使用弗洛伊德算法呢
一、初始化
首先为图中所有顶点对(i, j)之间设置一个距离矩阵D其中D[i][j]表示从顶点i到顶点j的当前已知最短距离。如果两个顶点之间没有直接相连的边则设置D[i][j]为一个很大的数通常是一个无穷大的值表示为∞。如果两个顶点之间有直接相连的边则设置D[i][j]为该边的权值。另外设置一个中间矩阵P用于记录最短路径的信息。
二、添加中间点
对于图中的每一个顶点k作为中间点遍历所有顶点对(i, j)其中i和j是图中的顶点且i ≠ ji ≠ kj ≠ k。如果从i到k再到j的路径比已知的i到j的路径更短即dist[i][k] dist[k][j] dist[i][j]则更新dist[i][j]为dist[i][k] dist[k][j]。
三、迭代
重复步骤二对于图中的每一个顶点k都执行一次。由于图中总共有n个顶点因此这个步骤需要执行n次迭代。
四、得出结果
在完成所有迭代后dist矩阵将包含图中所有顶点对之间的最短路径长度。如果dist[i][j]的值仍然是无穷大则表示从顶点i到顶点j没有路径。 时间复杂度
Floyd算法的时间复杂度为O(n^3)其中n是图中顶点的数量。这是因为算法需要进行n次迭代每次迭代都需要检查所有n^2个顶点对。 代码实现
下面是大家期待的代码实现今天我们用python实现
import numpy as np def floyd_warshall(graph): n len(graph) # 复制邻接矩阵作为距离矩阵 dist np.copy(graph) # 遍历所有顶点作为中间点 for k in range(n): # 遍历所有顶点对 (i, j) for i in range(n): for j in range(n): # 如果通过顶点 k 可以找到更短的路径 if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist # 示例图邻接矩阵
graph np.array([ [0, 5, float(inf), 10], [float(inf), 0, 3, float(inf)], [float(inf), float(inf), 0, 1], [float(inf), float(inf), float(inf), 0]
]) # 调用 Floyd-Warshall 算法
distances floyd_warshall(graph) # 打印结果
print(Shortest distances between all pairs of vertices:)
print(distances) 结束语
以上就是今天对弗洛伊德算法求解最短路径的解释希望对大家有所帮助如果对您有帮助希望您可以留下一个点赞、关注和收藏这对我很重要谢谢
