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

1、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 表示赋权图中从

2、结点vi 到 vj 的” 最短” 路径的长度 , 这条路上除了可能有 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

3、 的边的长度， pathi,j= i；否则 di,j=， pathi,j=-1 step 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 退出2 （二）程序框图参考主程序框图int i,j,k初初初初初 a初pfor(k=0;kd;k+) /初初初初

4、 a初pfor(i=0;id;i+) for(j=0;jaik+akjaij=aik+akj;pathij=k;ny初初初初初初 pfor(i=0;id;i+)/初初初初初初for(j=0;j ”,x);/ 打印中间结点dist(first,x);/ 递归调用dist(x,end); 3 七、测试用例：1、输入成本邻接矩阵： d：06380532290141003210vvvvvvvv（其中可用某个足够大的数据值代替，比如100）可得最短路径矩阵： p：131132122211111010103210vvvvvvvv以及各顶点之间的最短路径和最短路径长度：从 v0 到 v1 的最短路径长度为：

5、 1 ；最短路径为： v0v1 从 v0 到 v2 的最短路径长度为： 9 ；最短路径为： v0v1v3v2 从 v0 到 v3 的最短路径长度为： 3 ；最短路径为： v0v1v3 从 v1 到 v0 的最短路径长度为： 11；最短路径为： v1v3v2v0 从 v1 到 v2 的最短路径长度为： 8 ；最短路径为： v1v3v2 从 v1 到 v3 的最短路径长度为： 2 ；最短路径为： v1v3 从 v2 到 v0 的最短路径长度为： 3 ；最短路径为： v2v0 从 v2 到 v1 的最短路径长度为： 4 ；最短路径为： v2v0v1 从 v2 到 v3 的最短路径长度为： 6 ；最短

6、路径为： v2v0v1v3 从 v3 到 v0 的最短路径长度为： 9 ；最短路径为： v3v2v0 从 v3 到 v1 的最短路径长度为： 10；最短路径为： v3v2v0v1 从 v3 到 v2 的最短路径长度为： 6 ；最短路径为： v3v2 参考程序：#include #define infinity 100 #define max 10 int amaxmax,pmaxmax; main() void print_flod(int d); 4 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_fl