文档库

最新最全的文档下载
当前位置:文档库 > 实验三 最短路径的算法

实验三 最短路径的算法

实验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外没有其它结点

┉┉┉

根据此定义,D k[i,j]=min{ D k-1[i,j] , D k-1[i,k-1]+D k-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

若D k-1[i,k]+D k-1[k,j]

[结束循环]

[结束Step 3循环]

[结束Step 2循环]

Step 5 退出

(二)程序框图参考

主程序框图

实验三 最短路径的算法

其中,打印最短路径中间结点调用递归函数dist(),其框图如下,其中fist,end是当前有向边的起点和终点

dist(int first, int end)

实验三 最短路径的算法

七、测试用例:

1、输入成本邻接矩阵:D :063

8053

22901410

03

210∝∝∝

∝V V V V V V V V (其中∝可用某个足够大的数据值代替,比如100)

可得最短路径矩阵:P :1

31132

1222111110

10103

210--------V V V V V V V V

以及各顶点之间的最短路径和最短路径长度:

从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

2、程序运行界面参考:

实验三 最短路径的算法