弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解)

这篇具有很好参考价值的文章主要介绍了弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

弗洛伊德算法,是一种用于寻找图形中所有最短路径的算法。它的基本思想是通过一定的规则逐步更新每个节点的最短路径估计值,直到每个节点的最短路径估计值收敛为止。

具体来说,弗洛伊德算法通过求解所有点对之间的最短路径来实现。在算法开始时,我们假设图中的所有节点之间都是不联通的,即它们之间的距离为无穷大。然后,我们对图进行“松弛”操作,即尝试更新每个节点之间的距离估计值,以寻找更短的路径。具体来说,对于图中的每个节点对(i,j),我们检查是否存在一个节点k,使得从i到k再到j的路径比已知的最短路径更短。如果是的话,我们就更新(i,j)之间的距离估计值为更短的路径长度。

通过重复这个过程,我们最终得到了图中所有节点之间的最短路径估计值。弗洛伊德算法的时间复杂度为O(n^3),其中n是图中节点的数量。

弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解),图,1024程序员节,算法,数据结构,c语言,排序算法,图

邻接矩阵为

弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解),图,1024程序员节,算法,数据结构,c语言,排序算法,图

弗洛伊德算法

每次都选一个顶点作为中转点

第一次将V0作为中转点

对所有顶点i,j做判断dist[i][j]>dist[i][k]+dist[k][j] (k为此时的中转点

弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解),图,1024程序员节,算法,数据结构,c语言,排序算法,图

第二次将V1作为中转点

再次对所有顶点i,j做判断dist[i][j]>dist[i][k]+dist[k][j] (k为此时的中转点

弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解),图,1024程序员节,算法,数据结构,c语言,排序算法,图

第三次将V2作为中转点

对所有顶点i,j做判断dist[i][j]>dist[i][k]+dist[k][j] (k为此时的中转点

弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解),图,1024程序员节,算法,数据结构,c语言,排序算法,图

就得到了最终结果

下面我们来看一下代码是如何实现的(c语言代码实现)

void floyd(int graph[n][n])//弗洛伊德求各顶点之间的最短路径
{
	int dist[n][n];
	for (int i = 0; i < n; i++)//初始化距离矩阵
	{
		for (int j = 0; j < n; j++)
			dist[i][j] = graph[i][j];
	}
	for (int k = 0; k < n; k++)//逐一考虑每个顶点作为中间顶点
	{
		for (int i = 0; i < n; i++)//
		{
			for (int j = 0; j < n; j++)
			{
				if (dist[i][j] > dist[i][k] + dist[k][j])//k作为中间顶点,可以缩短(i,j)的距离
					dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (dist[i][j] != Max)
				printf("%d\t", dist[i][j]);
			else
				printf("Max");
		}
		printf("\n");
	}
}

完整测试代码

#include<stdio.h>
#define Max 0xFFFF
#define n 3
void floyd(int graph[n][n])//弗洛伊德求各顶点之间的最短路径
{
	int dist[n][n];
	for (int i = 0; i < n; i++)//初始化距离矩阵
	{
		for (int j = 0; j < n; j++)
			dist[i][j] = graph[i][j];
	}
	for (int k = 0; k < n; k++)//逐一考虑每个顶点作为中间顶点
	{
		for (int i = 0; i < n; i++)//
		{
			for (int j = 0; j < n; j++)
			{
				if (dist[i][j] > dist[i][k] + dist[k][j])//k作为中间顶点,可以缩短(i,j)的距离
					dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (dist[i][j] != Max)
				printf("%d\t", dist[i][j]);
			else
				printf("Max");
		}
		printf("\n");
	}
}
int main()
{
	int graph[n][n] = { {0,6,13},{10,0,4} ,{5,Max,0} };
	floyd(graph);
	return 0;
}

弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解),图,1024程序员节,算法,数据结构,c语言,排序算法,图

 文章来源地址https://www.toymoban.com/news/detail-713254.html

到了这里,关于弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法——弗洛伊德算法(Floyd-Warshall)(图论)(c++)

    (蒟蒻的第四篇文章,希望dalao勿喷) (希望没问题) 声明: 1.本人变量定义的名称很low 2.本人用的方法也很low 3.但我觉得文章应该不low  (盲目自信) 第四篇文章讲讲Floyd算法 Floyd算法是一种寻找最短路径的常见算法,其特点是: 短,好理解(虽然其他算法也挺好理解的

    2023年04月09日
    浏览(32)
  • 大话数据结构-迪杰斯特拉算法(Dijkstra)和弗洛伊德算法(Floyd)

      最短路径,对于图来说,是两顶点之间经过的边数最少的路径;对于网来说,是指两顶点之间经过的边上权值之和最小的路径。路径上第一个顶点为源点,最后一个顶点是终点。   以如下无向图为例:   我们来计算下标为0的顶点,到其他顶点的最短路径,首先定义

    2024年02月06日
    浏览(39)
  • 最短路径——弗洛伊德算法

    对于这类最短路径问题,DIF算法也可以解决,只需要 定义一个二维数组 ,以 数组的横坐标作为有向网顶点的下标 , 循环n次 依次求解各个源点到其余顶点的最短路径, 时间复杂度为O(n^3) 。 由于弗洛伊德算法求解该问题的的时间复杂度同为O(n^3),而且 思路简单及代码实现

    2024年01月23日
    浏览(41)
  • 弗洛伊德循环查找算法-原理

    本文灵感来自哔哩哔哩视频  视频链接: 弗洛伊德循环查找算法 算法代码(java) 弗洛伊德循环查找算法中第二次相遇的地方就是循环的起始点,这个性质的证明是基于数学的原理。这是因为在第一次相遇时,慢指针 `slow` 和快指针 `fast` 已经处于同一个循环内。设链表起点到环

    2024年01月19日
    浏览(43)
  • 弗洛伊德算法(求最短路径)

    在一个加权图中,如果想找到各个顶点之间的最短路径,可以考虑使用弗洛伊德算法。 弗洛伊德算法既适用于无向加权图,也适用于有向加权图。使用弗洛伊德算法查找最短路径时,只允许环路的权值为负数,其它路径的权值必须为非负数,否则算法执行过程会出错。 弗洛

    2024年02月06日
    浏览(43)
  • 今天学习了弗洛伊德算法(floyed)

    我自己写的模板 嘿嘿 Dijkstra算法SPFA算法但是我知道还有这些,但是今天是周末哎,我有点不想学了,我今天学的是比较差劲的一个算法(但是它好像比较好记啊),改天再学其他比较好一点的算法加强自己 输入 输出 后言:提醒自己加权值是分题目来不同权值,不是像示例

    2024年02月11日
    浏览(33)
  • 力扣-202. 快乐数解析-弗洛伊德循环查找算法

    题目链接   使用代码测试一下每一代数字  可以发现 归纳一下这些简单数字就可以发现,对于任意一个非快乐数,最终会进入重复循环, ···不难发现,4即之后的结果就是新一轮循环。 那么我的第一个做法是检测4出现的次数 如果4出现次数超过两次, 那么就不是快乐数 感

    2024年01月20日
    浏览(37)
  • 【数据结构】最短路径算法实现(Dijkstra(迪克斯特拉),FloydWarshall(弗洛伊德) )

    最短路径问题 :从在带权有向图G中的某一顶点出发,找出一条通往另一顶点的最短路径,最短也就是沿路径各边的权值总和达到最小。 单源最短路径问题:给定一个图G = ( V , E ) G=(V,E)G=(V,E),求源结点s ∈ V s∈Vs∈V到图 中每个结点v ∈ V v∈Vv∈V的最短路径 针对一个带权

    2024年02月04日
    浏览(47)
  • 【力扣热题100】287. 寻找重复数(弗洛伊德的乌龟和兔子方法)

    刷一道力扣热题100吧 难度中等 https://leetcode.cn/problems/find-the-duplicate-number/?envType=study-plan-v2envId=top-100-liked 一年半前做过这题,但是时间复杂度不够。现在重新学一下 主要是用到了弗洛伊德的乌龟和兔子方法 算法预览: 初始化 :从两个指针开始,“乌龟\\\"和\\\"兔子”,都指向第

    2024年02月05日
    浏览(56)
  • 数据结构第13周 :( 迪杰斯特拉最短路径 + 弗洛伊德求最短路径 + 欧拉回路 + Invitation Cards)

    【问题描述】 在带权有向图G中,给定一个源点v,求从v到G中的其余各顶点的最短路径问题,叫做单源点的最短路径问题。 在常用的单源点最短路径算法中,迪杰斯特拉算法是最为常用的一种,是一种按照路径长度递增的次序产生最短路径的算法。 在本题中,读入一个有向图

    2024年02月13日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包