大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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算法解题步骤
以下纯手工操作~
上面最后有个问题,更正一下,应该是
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;
}
城市数据 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 表示不可直达,运行结果如下:
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234079.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...