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

实验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的后继结点 四、实验要求

要求输出每对结点之间的最短路径长度以及其最短路径

五、实验步骤

（一）算法描述

Step 1 初始化有向图的成本邻矩阵D、路径矩阵path

若从结点vi到vj有边，则D[i,j]= vi到vj的边的长度，path[i,j]= i；

否则D[i,j]=?， path[i,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-1[i,k]+Dk-1[k,j]

[结束循环]

[结束Step 3循环] [结束Step 2循环]

Step 5 退出

1

（二）程序框图参考 主程序框图

int i,j,k初初初初初a初Pfor(k=0;ka[i][k]+a[k][j]Na[i][j]=a[i][k]+a[k][j];path[i][j]=k;初初初初初初Pfor(i=0;i

dist(int first, int end)int x; //存放最短路径的中间结点x=path[first][end]Y x==first N printf(“V%d->”,x);//打印中间结点dist(first,x);//递归调用dist(x,end);

2

七、测试用例：

V0V1V2V3V01、输入成本邻接矩阵：D：V10?3?105??90642 80V2V3（其中?可用某个足够大的数据值代替，比如100）

V0V1V2V3V0?10?1101

可得最短路径矩阵：P：V1?1?1V222?12V3?1?13?1以及各顶点之间的最短路径和最短路径长度：

从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 参考程序： #include #define INFINITY 100 #define Max 10

int a[Max][Max],P[Max][Max]; main() {

void Print_Flod(int d);

3