实验三-最短路径的算法(离散数学实验报告)

1实验3：最短路径算法一、实验目的通过本实验的学习，理解Floyd（弗洛伊得）最短路径算法的思想二、实验内容用C语言编程实现求赋权图中任意两点间最短路径的Floyd算法，并能对给定的两结点自动求出最短路径三、实验原理、方法和手段1、Floyd算法的原理定义：Dk[i,j]表示赋权图中从结点vi出发仅通过v0，v1，┉，vk-1中的某些结点到达vj的最短路径的长度，若从vi到vj没有仅通过v0，v1，┉，vk-1的路径，则D[i,j]=即D-1[i,j]表示赋权图中从结点vi到vj的边的长度，若没有从结点vi到vj的边，则D[i,j]=D0[i,j]表示赋权图中从结点vi到vj的”最短”路径的长度,这条路上除了可能有v0外没有其它结点D1[i,j]表示赋权图中从结点vi到vj的”最短”路径的长度,这条路上除了可能有v0，v1外没有其它结点┉┉┉根据此定义，Dk[i,j]=min{Dk-1[i,j],Dk-1[i,k-1]+Dk-1[k-1,j]}定义：path[i,j]表示从结点vi到vj的“最短”路径上vi的后继结点四、实验要求要求输出每对结点之间的最短路径长度以及其最短路径五、实验步骤（一）算法描述Step1初始化有向图的成本邻矩阵D、路径矩阵path若从结点vi到vj有边，则D[i,j]=vi到vj的边的长度，path[i,j]=i；否则D[i,j]=，path[i,j]=-1Step2刷新D、path对k=1,2,┉n重复Step3和Step4Step3刷新行对i=1,2,┉n重复Step4Step4刷新Mij对j=1,2,┉n若Dk-1[i,k]+Dk-1[k,j]Dk-1[i,j]，则置Dk[i,j]=Dk-1[i,k]+Dk-1[k,j]，path[i,j]=k；否则不变[结束循环][结束Step3循环][结束Step2循环]Step5退出2（二）程序框图参考主程序框图inti,j,k初初初初初a初Pfor(k=0;kD;k++)//初初初初a初Pfor(i=0;iD;i++)for(j=0;jD;j++)a[i][j]a[i][k]+a[k][j]a[i][j]=a[i][k]+a[k][j];path[i][j]=k;NY初初初初初初Pfor(i=0;iD;i++)//初初初初初初for(j=0;jD;j++)printf(fromV%dtoV%d:,i,j);dist(i,j);//初初初初,初初初初初初printf(V%d,j);//初初初初初初初初printf((Thelengthis:%d),a[i][j]);printf(\n);//初初初初i==jNY其中，打印最短路径中间结点调用递归函数dist()，其框图如下，其中fist,end是当前有向边的起点和终点dist(intfirst,intend)intx;//存放最短路径的中间结点x=path[first][end]Yx==firstNprintf(“V%d-”,x);//打印中间结点dist(first,x);//递归调用dist(x,end);3七、测试用例：1、输入成本邻接矩阵：D：06380532290141003210VVVVVVVV（其中可用某个足够大的数据值代替，比如100）可得最短路径矩阵：P：131132122211111010103210VVVVVVVV以及各顶点之间的最短路径和最短路径长度：从V0到V1的最短路径长度为：1；最短路径为：V0→V1从V0到V2的最短路径长度为：9；最短路径为：V0→V1→V3→V2从V0到V3的最短路径长度为：3；最短路径为：V0→V1→V3从V1到V0的最短路径长度为：11；最短路径为：V1→V3→V2→V0从V1到V2的最短路径长度为：8；最短路径为：V1→V3→V2从V1到V3的最短路径长度为：2；最短路径为：V1→V3从V2到V0的最短路径长度为：3；最短路径为：V2→V0从V2到V1的最短路径长度为：4；最短路径为：V2→V0→V1从V2到V3的最短路径长度为：6；最短路径为：V2→V0→V1→V3从V3到V0的最短路径长度为：9；最短路径为：V3→V2→V0从V3到V1的最短路径长度为：10；最短路径为：V3→V2→V0→V1从V3到V2的最短路径长度为：6；最短路径为：V3→V2参考程序：#includestdio.h#defineINFINITY100#defineMax10inta[Max][Max],P[Max][Max];main(){voidPrint_Flod(intd);4inti,j,k,D=4;printf(请输入成本邻接矩阵：\n);for(i=0;iD;i++)for(j=0;jD;j++){scanf(%d,&a[i][j]);}for(i=0;iD;i++)for(j=0;jD;j++){if(a[i][j]0&&a[i][j]INFINITY)P[i][j]=i;elseP[i][j]=-1;}for(k=0;kD;k++)for(i=0;iD;i++)for(j=0;jD;j++)if(a[i][k]+a[k][j]a[i][j]){a[i][j]=a[i][k]+a[k][j];P[i][j]=k;}Print_Flod(D);}voidPrint_Flod(intd){voiddist(intfirst,intend);inti,j;for(i=0;id;i++)for(j=0;jd;j++)if(i!=j)5{printf(fromV%dtoV%d:,i,j);dist(i,j);printf(V%d,j);printf((Thelengthis:%d)\n,a[i][j]);}}voiddist(intfirst,intend){intx;x=P[first][end];if(x!=first){dist(first,x);dist(x,end);}elseprintf(V%d-,x);}输出结果：