《实验三 最短路径的算法.docx》由会员分享，可在线阅读，更多相关《实验三 最短路径的算法.docx（6页珍藏版）》请在三一办公上搜索。
1、实验三 最短路径的算法实验3：最短路径算法 一、实验目的 通过本实验的学习，理解Floyd最短路径算法的思想 二、实验内容 用C语言编程实现求赋权图中任意两点间最短路径的Floyd算法，并能对给定的两结点自动求出最短路径 三、实验原理、方法和手段 1、Floyd算法的原理 定义：Dki,j 表示赋权图中从结点vi出发仅通过v0，v1，vk-1中的某些结点到达vj的最短路径的长度， 若从vi到vj没有仅通过v0，v1，vk-1 的路径，则Di,j= 即 D-1i,j 表示赋权图中从结点vi到vj的边的长度，若没有从结点vi到vj的边，则Di,j= D0i,j 表示赋权图中从结点vi到vj的”最短
2、”路径的长度, 这条路上除了可能有v0外没有其它结点 D1i,j 表示赋权图中从结点vi到vj的”最短”路径的长度, 这条路上除了可能有v0，v1外没有其它结点 根据此定义，Dki,j=min Dk-1i,j , Dk-1i,k-1+Dk-1k-1,j 定义：pathi,j表示从结点vi到vj的“最短”路径上vi的后继结点 四、实验要求 要求输出每对结点之间的最短路径长度以及其最短路径 五、实验步骤 算法描述 Step 1 初始化有向图的成本邻矩阵D、路径矩阵path 若从结点vi到vj有边，则Di,j= vi到vj的边的长度，pathi,j= i； 否则Di,j=， pathi,j=-1 S
3、tep 2 刷新D、path 对k=1,2,n 重复Step 3和Step 4 Step 3 刷新行 对 i=1,2,n 重复Step 4 Step 4 刷新Mij 对 j=1,2,n 若Dk-1i,k+Dk-1k,j Dk-1i,j ，则置Dki,j= Dk-1i,k+Dk-1k,j，pathi,j=k；否则不变 结束循环 结束Step 3循环 结束Step 2循环 Step 5 退出 1 程序框图参考 主程序框图 int i,j,k初初初初初a初Pfor(k=0;kD;k+) /初初初初a初Pfor(i=0;iD;i+) for(j=0;jaik+akjNaij=aik+akj;pathi
4、j=k;初初初初初初Pfor(i=0;iD;i+)/初初初初初初for(j=0;j”,x);/打印中间结点dist(first,x);/递归调用dist(x,end); 2 七、测试用例： V0V1V2V3V01、输入成本邻接矩阵：D：V10310590642 80V2V3V0V1V2V3V0-10-1101 可得最短路径矩阵：P：V1-1-1V222-12V3-1-13-1以及各顶点之间的最短路径和最短路径长度： 从V0到V1的最短路径长度为：1 ；最短路径为：V0V1 从V0到V2的最短路径长度为：9 ；最短路径为：V0V1V3V2 从V0到V3的最短路径长度为：3 ；最短路径为：V0V1
5、V3 从V1到V0的最短路径长度为：11；最短路径为：V1V3V2V0 从V1到V2的最短路径长度为：8 ；最短路径为：V1V3V2 从V1到V3的最短路径长度为：2 ；最短路径为：V1V3 从V2到V0的最短路径长度为：3 ；最短路径为：V2V0 从V2到V1的最短路径长度为：4 ；最短路径为：V2V0V1 从V2到V3的最短路径长度为：6 ；最短路径为：V2V0V1V3 从V3到V0的最短路径长度为：9 ；最短路径为：V3V2V0 从V3到V1的最短路径长度为：10；最短路径为：V3V2V0V1 从V3到V2的最短路径长度为：6 ；最短路径为：V3V2 参考程序： #include #de
6、fine INFINITY 100 #define Max 10 int aMaxMax,PMaxMax; main void Print_Flod(int d); 3 int i,j,k,D=4; printf(请输入成本邻接矩阵：n); for(i=0;iD;i+) for(j=0;jD;j+) scanf(%d,&aij); for(i=0;iD;i+) for(j=0;j0& aijINFINITY) Pij=i; else Pij=-1; for(k=0;kD;k+) for(i=0;iD;i+) for(j=0;jD;j+) if (aik+akjaij) aij=aik+akj; Pij=k; Print_Flod(D); void Print_Flod(int d) void dist(int first,int end); int i,j; for(i=0;id;i+) for(j=0;j,x); 输出结果： 5
