Robert W.Floyd和Stephen Warshall在1962年发表了Floyd-Warshall算法
如图,有1234,四个点,每个点都有一定的距离,比如1和2有2的距离,现在我想知道任意两个点的最短距离。
我先用“邻接矩阵存储法”将这个图转化为矩阵
竖坐标是出发点,横坐标是目的地,∞表示无穷大,也就是到不了,例如2到不1。有了这个矩阵,就可以用一个两维数组来存储。
现在切入重点:Floyd-Warshall算法。
拿从4到3来看,4到3直达为12,要想缩短,只有“换乘”。
我发现4还可以直达1,1换乘到3,这时距离为11,比直达要短。那有什么比这个还短的?到1时再换乘!不要走直达。我发现1可以到2,2换乘到3,这时距离为10,又短了。
我发现每个点都可以作为“换乘点”,先初始化直达的距离,再把1作为“换乘点”,计算出新的最短距离,再把1和2作为“换乘点”。。。最后1234全作为“换乘点”。这就是Floyd-Warshall算法的基本思想,现在上代码:
#include <stdio.h> int main() { int a[10][10], n, m, i, j, k, t1, t2, t3; int inf = 99999999;//这里定义的正无穷 //读入nm,n为顶点数,m为边的条数 scanf("%d %d", &n, &m); //初始化矩阵 for (i = 1; i <= n; i++) for(j = 1; j <= n; j++) if(i == j)a[i][j] = 0; else a[i][j] = inf; //读入边 for(i = 1; i <= m; i++) { scanf("%d %d %d", &t1, &t2, &t3); a[t1][t2] = t3; } //Floyd-Warshall算法核心代码 for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) for(k = 1; k <= n; k++) if(a[j][i] < inf && a[i][k] < inf && a[j][k] > a[j][i] + a[i][k]) a[j][k] = a[j][i] + a[i][k]; //输出最终结果 for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { printf("%10d", a[i][j]); } printf("\n"); } return 0; }
输入:
4 8 1 2 2 1 3 6 1 4 4 2 3 3 3 1 7 3 4 1 4 1 5 4 3 12
得出结果:
0 2 5 4 9 0 3 4 6 8 0 1 5 7 10 0
Floyd-Warshall算法思路貌似很复杂,但它的核心代码只有五行,时间复杂度是O(N3),如果我只想知道某一个点到其它点的最短距离,用这套算法就感觉太耗时了。算法发表者Robert W.Floyd也是图灵奖的获得者(屌爆了)。
相关推荐
**Floyd-Warshall算法**是一种著名的图论算法,用于解决多对多的最短路径问题。在图中,每个节点代表一个实体,每条边表示两个实体之间的关系,可以是带权重的距离或其他衡量标准。Floyd-Warshall算法的核心思想是...
在图论中,Floyd-Warshall算法是一种用于解决图中所有顶点对之间最短路径问题的著名算法。它由Robert Floyd和Stephen Warshall独立提出,适用于处理有权图,包括有向图和无向图,无论是权重为正还是负(但不包括负权...
1.版本:matlab2022A,包含...将Floyd-Warshall算法应用于ISOMAP中,可以计算数据点之间的最短路径距离,进而用于降维。 5.注意事项:注意MATLAB左侧当前文件夹路径,必须是程序所在文件夹位置,具体可以参考视频录。
Floyd-Warshall算法是一种经典的图论算法,用于解决图中任意两个顶点之间的最短路径问题。这个算法尤其适用于稠密图,即边的数量接近于顶点数量平方的图,因为它的时间复杂度是O(n^3),其中n是图中的顶点数。相比...
Floyd-Warshall算法是一种高效的算法,用于寻找赋权图中各结点之间的最短距离。该算法不仅适用于权值大于等于零的常见问题,也可以用于权值小于零的问题。 Floyd-Warshall算法的主要思想是,通过多次迭代,逐步计算...
Floyd-Warshall算法是一种经典的图论算法,用于求解所有顶点对之间的最短路径。这个算法由Robert Floyd和Stephen Warshall独立提出,因此得名。在C++编程语言中实现Floyd-Warshall算法,可以高效地解决大规模网络中...
深度优先搜索 DFS、广度优先搜索 BFS)、最短路径(Dijkstra 算法、Floyd-Warshall 算法
Floyd-Warshall算法是一种基于动态规划(Dynamic Programming)的最短路径算法,用来求解任意两点间的最短距离。时间复杂度为O(n^3)。在这里,我们将对Floyd-Warshall算法的DP流程进行详细的解释。 首先,让我们看...
Floyd-Warshall算法是一种用于寻找图中所有节点之间的最短路径的算法。该算法可以解决旅游时行程规划问题,即找到从一个城市到另一个城市的最短路径。 原理是,两个城市之间的路程可能会大于两个城市经过一个中转...
算法课程实验里的题目,简单的用Floyd-Warshall实现有向图最短路径查找
代码实现了Floyd-Warshall算法,它接受一个带权重的有向图作为输入,计算出任意两个节点之间的最短路径。 在示例代码中,使用graph二维数组表示图的邻接矩阵,Integer.MAX_VALUE表示两个节点之间不存在直接连接。...
Floyd-Warshall 算法计算给定邻接矩阵的所有对最短路径矩阵。 该算法是 O(n^3),在大多数实现中,您会看到 3 个嵌套的 for 循环。 这在 Matlab 中效率很低,所以在这个版本中,两个内部循环被向量化(因此,它运行得...
Floyd-Warshall算法是一种经典的图论算法,主要用于求解所有顶点对之间的最短路径问题。在实际的计算机科学与信息技术领域,这个算法有着广泛的应用,比如在网络路由、物流规划、社会网络分析等方面。下面将详细介绍...
标题中的"Floyd_Floydmatlab_最短路径算法_源码.zip"暗示了这是一个使用MATLAB编程语言实现的Floyd-Warshall算法的源代码集合。Floyd-Warshall算法是一种在图论中用于查找所有节点对之间的最短路径的经典算法,特别...
Floyd-Warshall算法,由Robert Floyd和Stephen Warshall独立提出,主要用于求解有向或无向带权重图的最短路径问题。该算法基于动态规划思想,通过迭代的方式逐步完善最短路径信息。其核心在于每次尝试通过中间节点来...
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程...
要找出所有点对的最短路径,我们需要解决的是多源最短路径问题,这与单源最短路径问题(例如Dijkstra算法或Floyd-Warshall算法)有所不同。 1. **问题定义**: 所有点对最短路径问题是指在带权有向或无向图中,找...
-- 输入权重(或初始距离)矩阵必须具有节点未连接的 ... -- 输出是短路径的距离矩阵 D 和前任矩阵 P 使得 P(i,j) 是从 i 到 j 的最短路径上 j 之前的节点,因此如果要构建路径,则必须读取 P向后。 希望能帮助到你!
标题中的"Floyd最短路径程序(MFC)"指的是利用Floyd-Warshall算法在MFC(Microsoft Foundation Classes)框架下开发的一个图形用户界面程序,用于计算图中所有顶点之间的最短路径。MFC是微软提供的C++类库,用于构建...
标题提及的是“两点之间的最短路径(Floyd算法)源代码”,这指的是使用Floyd-Warshall算法解决图论中的经典问题——寻找图中任意两点间的最短路径。Floyd-Warshall算法是一种动态规划方法,能够处理带有负权重的边...