<s id="mvh2b"><strike id="mvh2b"><u id="mvh2b"></u></strike></s>
    1. <rp id="mvh2b"></rp>

      当前位置:首页 > IT教程

      Floyd算法详解——包括解题步骤与编程

      时间:2021-08-06 04:53:09来源:金橙教程网 作者:admin8 阅读:65次 [手机版]
       

      floyd算法

      一、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 表示不可直达,运行结果如下:

      相关阅读

      几种常见模式识别算法整理和总结

      这学期选了门模式识别的课。发现最常见的一种情况就是&#xff0c;书上写的老师ppt上写的都看不懂&#xff0c;然后绕了一大圈去自己查资

      遗传算法详解及代码实现

      遗传算法 定义相关术语交叉变异产生子代完整过程 遗传

      【原创】【算法】三点定位简述

      插叙&#xff1a;本想着每月都写呢&#xff0c;但是后来最近几个月工作和家庭太忙了&#xff0c;真是没时间写&#xff0c;且写且珍惜。 一、这是

      操作系统:进程调度算法详解之FCFS和SPF篇

      前言&#xff1a; 在学习操作系统的时候&#xff0c;总是可以听到一些与“调度”相关的东西。记得刚学计算机操作系统的时候&#xff0c;总是

      FFT算法

      FFT算法 分类&#xff1a;?信号处理 2008-04-19 21:03? 2582人阅读? 评论(1)? 收藏? 举报 这几天&#xff0c;我一直

      分享到:

      IT相关

      程序相关

      推荐文章

      热门文章

      东北老女人嫖老头视频_无遮挡H肉动漫视频在线观看_欧美牲交a欧美牲交aⅴ另类_狼人乱码无限2021芒果