Floyd算法详解——包括解题步骤与编程[通俗易懂]

Floyd算法详解——包括解题步骤与编程[通俗易懂]一、Floyd算法原理Floyd算法是一个经典的动态规划算法,它又被称为插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,算法目标是寻找从点i到点j的最短路径。从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

一、Floyd算法原理

Floyd算法是一个经典的动态规划算法,它又被称为插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,算法目标是寻找从点i到点j的最短路径。

从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。所以,算法假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,算法检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,便设置Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当遍历完所有节点k,Dis(i,j)中记录的便是i到j的最短路径的距离。

二、Floyd算法内容步骤

(一)Floyd算法内容

Floyd算法详解——包括解题步骤与编程[通俗易懂]

(二)Floyd算法步骤

Floyd算法详解——包括解题步骤与编程[通俗易懂]

三、Floyd算法解题步骤

以下纯手工操作~

Floyd算法详解——包括解题步骤与编程[通俗易懂]

Floyd算法详解——包括解题步骤与编程[通俗易懂]

Floyd算法详解——包括解题步骤与编程[通俗易懂]

Floyd算法详解——包括解题步骤与编程[通俗易懂]

上面最后有个问题,更正一下,应该是

eg:d13 = 45,R13 = 5,R15 = 5(或者)R51 = 1,也就是13之间经过5,然后再看15之间有没有经过其他点,如果经过了继续查表,由于通过R15或R51可以看出,他们之间没有经过其他点,所以最短路径为1-》5-》3,最短距离为45.

四、Floyd算法编程

编程求解几座城市之间的最短距离,以及最短距离所经过的城市。

floyd.c:

#include <string.h>   
#include <stdio.h>  

#define NUMS 12   
#define INF 65535

typedef struct  
{   
    	char vertex[NUMS];   
    	int edges[NUMS][NUMS];   
    	int n,e;   
}Graph;   

void Dispath(int A[][NUMS],int path[][NUMS],int n); 

void ReadGraph(Graph *G)   
{   
	int i,j;
	FILE * fp = fopen("floyd.txt","rw");
	G->n = NUMS;
	G->e = NUMS * NUMS; 
	for(i=0; i<NUMS; i++)
	{
		for(j=0; j<NUMS; j++)
		{
			fscanf(fp,"%d",&(G->edges[i][j]));
			printf("%d \t",G->edges[i][j]);			
		}
		printf("\n");
	}
}   

void Floyd(Graph G)
{
	int A[NUMS][NUMS],path[NUMS][NUMS];
	int i,j,k;
	for (i=0;i<G.n;i++)
	{
		for (j=0;j<G.n;j++)
		{
			A[i][j]=G.edges[i][j];
			path[i][j]=-1;
		}
	}
	for (k=0;k<G.n;k++)
	{
		for (i=0;i<G.n;i++)
		{
			for (j=0;j<G.n;j++)
			{
				if (A[i][j]>A[i][k]+A[k][j])
				{
					A[i][j]=A[i][k]+A[k][j];
					path[i][j]=k;
				}
			}
		}
	}
	Dispath(A,path,G.n);
}
 
void Ppath(int path[][NUMS],int i,int j)
{
	int k;
	k=path[i][j];
	if (k==-1)
	{
		return;
	}
	Ppath(path,i,k);
	printf("%d,",k + 1);
	Ppath(path,k,j);
}
 
void Dispath(int A[][NUMS],int path[][NUMS],int n)
{
	int i,j;
	for (i=0;i<n;i++)
	{
		for (j=0;j<n;j++)
		{
			if (A[i][j]==INF)
			{
				if (i!=j)
				{
					printf("从%d到%d没有路径\n",i+1,j+1);
				}
			}
			else
			{
				printf(" 从%d 到 %d => 最短路径长度为 : %d , 路径站点为 :",i+1,j+1,A[i][j]);
				printf("%d,",i + 1);
				Ppath(path,i,j);
				printf("%d\n",j + 1);
			}
		}
	}
}
 
int main()
{
	Graph G;
	ReadGraph(&G);
	Floyd(G);
	return 0;
}

Jetbrains全家桶1年46,售后保障稳定

城市数据 floyd.txt 如下:

0	20	65535	35	30	65535	65535	65535	65535	65535	65535	65535
20	0	25	65535	65535	65535	65535	65535	65535	65535	65535	65535
65535	25	0	5	65535	22	65535	65535	60	65535	75	65535
35	65535	5	0	65535	20	65535	65535	40	65535	65535	65535
30	65535	65535	65535	0	25	20	30	65535	65535	65535	65535
65535	65535	22	20	25	65535	12	40	65535	65535	65535	65535
65535	65535	65535	65535	20	65535	0	65535	65535	40	65535	65535
65535	65535	65535	65535	30	12	65535	0	35	65535	65535	90
65535	65535	65535	65535	65535	40	65535	35	0	30	35	45
65535	65535	65535	65535	65535	65535	40	65535	30	0	10	20
65535	65535	65535	65535	65535	65535	65535	65535	35	10	0	15
65535	65535	65535	65535	65535	65535	65535	90	45	20	15	0

其中 65535 表示不可直达,运行结果如下:

Floyd算法详解——包括解题步骤与编程[通俗易懂]

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234079.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Eclipse常见错误overlaps the location of another project: ‘xxx

    Eclipse常见错误overlaps the location of another project: ‘xxxEclipse常见错误overlaps the location of another project: ‘xxx

  • scala List immutable.Map[String,Any]]的排序问题

    scala List immutable.Map[String,Any]]的排序问题

  • CRT连接linux,新建的用户“oralce”可以登陆了,root就登录不了了。 /etc/ssh/sshd_config 找到 PermitRootLogin no 改为yes

    CRT连接linux,新建的用户“oralce”可以登陆了,root就登录不了了。 /etc/ssh/sshd_config 找到 PermitRootLogin no 改为yes=================配置安装oracle环境过程中可能修改了root登录限制。==========找到的办法:远程登录的话查看下/etc/ssh/sshd_config找如下的一句PermitRootLoginno改为如下的;PermitRootLoginyes不行的话cat/etc/security看下有没这么一行:SU_ROOT

  • idea怎么远程debug_idea 多线程调试

    idea怎么远程debug_idea 多线程调试1,远程DEBUG的必要性由于部署环境的差异性,相信很多朋友都碰到过开发环境正常测试过的功能在测试环境甚至生产环境下出现bug的情况。一般情况下,生产环境可以采取的手段比较单一,即通过日志的方式获取运行中的环境上下文,分析日志文件并尝试重现bug。这会带来的问题还是不少的,首先,日志的分析是一项比较耗时的工作;其次,现有的日志记录不一定能反映出问题,你可能需要多次重复这个过程(分析日志->猜测问题->加日志->部署->获取日志)来慢慢逼近问题。倘若是测试环境,我们还多了一项可..

  • eclipse汉化小教程

    eclipse汉化小教程点aboutEclipsexxx然后会显示版本http://www.eclipse.org/babel/downloads.php进入该网址一般都选择Mars(最后一个)复制网址http://download.eclipse.org/technology/babel/update-site/R0.15.1/mars加载出pending包后选择ChineseTraditional安装一路n…

  • 彻底禁止Win10自动更新工具Windows Update Blocker v1.5 汉化版

    彻底禁止Win10自动更新工具Windows Update Blocker v1.5 汉化版以往的Windows10系统我们还可以通过禁止更新服务,设置一些本地组策略来禁止Windows系统的更新,但现在的Windows好像越来越流行更新了,一些简单的禁止完全没用,依旧会自动检查更新!一款你需要的彻底禁止Win10自动更新的工具它来了,WindowsUpdateBlocker是一款免费软件,只需一键,即可帮助您完全禁用或启用Windows系统上的自动更新。使用起来超级…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号