最短路径实验报告

1、实验最短路径姓名：班 级：学号：试验时间：一、从某个源点到其余各顶点的最短路径1问题描述本实验实现dijkstra算法。图存储采用了数组存储结构。图类的定义为第9.1.1节图类的修改，仅保留了与本程序有关的成员函数，增添了一个求单源点最短路径的成员函数。2、算法设计源程序：template void MGraph:ShortestPath_DIJ(i nt vO,PathMatrix_1 & P,ShortPathTable &D)/用Dijkstra算法求有向网的 v0顶点到其余顶点 v的最短路径Pv及带权长度Dv。若Pvw为true，则w是从v0到v当前求得最短路径上的顶点。/finalv

2、为true当且仅当v S,即已经求得从 v0到v的最短路径int v,w,i,j,mi n;bool finalMAX_VERTEX_NUM; /辅助矩阵，为真表示该顶点到v0的最短距离已求出，初值为假for(v = O;vmgraph.vex nu m;v+)fin alv = false; / 设初值Dv = mgraph.arcsvOv.adj; / D 存放 v0 到 v 的最短距离，初值为 v0 到 v 的 直接距离for(w = 0;wmgraph.vex nu m;w+)/设空路径Pvw = false;if(Dvi nfin ity)/ v0到v有直接路径PvvO = Pvv

3、= true; /一维数组pv表示源点v0到v最短路径通过的顶点Dv0 = 0; / v0 到 v0 距离为 0finalv0 = true; / v0 顶点并入 S 集for(i = 1;imgraph.vex nu m;i+)/其余G.vexnum-1个顶点/开始主循环，每次求得v0到某个顶点v的最短路径，并将 v并入S集min = infinity; /当前所知离v0顶点的最近距离，设初值为for(w = O;wmgraph.vex nu m;w+)/对所有顶点检查if(!finalw&Dwmin)/在S集之外的顶点中找离 v0最近的顶点，并将其赋给v,距离赋给 minv = w;min

4、 = Dw;finalv = true; / 离v0最近的v并入S集for(w = 0;wmgraph.vex nu m;w+)根据新并入的顶点，更新不在S集的顶点到v0的距离和路径数组if(!fi nalw &mininfinity&mgraph.arcsvw.adj infinity&(mi n+mgraph.arcsvw.adjDw)/ w不属于S集且vOtvtw的距离 目前vOtw的距离Dw = min+mgraph.arcsvw.adj; / 更新 Dwfor(j = 0;jmgraph.vex nu m;j+)/修改Pw , v0到w经过的顶点包括 v0到v经过的顶点再加 上顶点w

5、Pwj = Pvj;Pww = true;3、运行与测试程序运行如图所示。G：l学习锻碍吉构实9 4DUDebugSPath_DU,exepI5 0数 网个 向的2 3 5 4 1 1 Z h c d d h c 为 8 a a c b e e 阵亠浅 有弧歧声挾城4S披城邻8 兔d占竄馬占竄占小諭 种占E H占皆告小占皆告小向U 3 1的顶起起起蕃起有左 + 占C 阳顶弧弧弧弧b 冋个A2亘nF2 3- haaaaaaaa 选选O88单*(00源点点的最短路径0 0 010 00 1010 10 0 01.2.3.4081888Stepl:运行程序，屏幕显示菜单。Step2：运行功能选择。C

6、asel:输入“1”选择菜单项1，进入图的创建操作。1.1根据屏幕提示，创建有向网。1.2屏幕显示网信息。Case2：输入“ 2”选择菜单项2，进入求源点到其他各点的距离操作。 屏幕显示求得源点到其他各点的距离和路径数组。Case3输入“ 3”选择菜单项3，结束程序运行。簟T=到各顶点的最短路径长度为:、每一对顶点之间的最短路径1问题描述本程序用于验证floyd算法。图采用了邻接表存储。图类的定义为第9.1.2节图类的修改，仅保留了与本程序用到的基本操作，增添了拓扑排序成员函数。2、算法设计源程序：template void MGraph:ShortestPath_FLOYD(PathMatr

7、ix_2 & P,Dista ncMatrix &D)用Floyd算法求有向网 G中各对顶点v和w之间的最短路径 Pvw及其带权长度 Dvw /若PVWU为TRUE，贝y u是从v到w当前求得最短路径上的顶点。int u,v,w,i;for(v = O;vmgraph.vex nu m;v+)/各对结点之间初始已知路径及距离for(w = 0;wmgraph.vex nu m;w+)Dvw = mgraph.arcsvw.adj;顶点 v 到顶点 w 的直接距离for(u = 0;umgraph.vex num ;u+)Pvwu = false;/ 路径矩阵初值 if(Dvwi nfin it

8、y)从v到w有直接路径Pvwv = Pvww = true;/ 由 v 到 w 的路径经过 v 和 w 两点 for(u = 0;umgraph.vex num ;u+)for(v = 0;vmgraph.vex nu m;v+)for(w = 0;wmgraph.vex nu m;w+)if(Dvu+DuwDvw) Dvw = Dvu+Duw;更新最短距离for(i = 0;imgraph.vex nu m;i+)Pvwi = Pvui|Puwi;3、运行与测试*G: 习 l數男当訥实 K9_E 94FLOYDDebugSPath_FLOYD.exew无向网3 5461132数K径1路 s-

9、 组之 ?- 采图对建-二 一 一 -h; 创囂矍入入入入入入入12 3*-4冃土冃土口土Ni.冃*旧士目主口主冃/顶VZ S 嘗取组之顶OO菜图对作建一翼创氢12 34 6 5-237M亠罔亠壘离亠禺亠罔 一 n-一 n一 n 一-n 一-n 一-n一 cm 毛一豆一口言竺一 口兰七一 I. Lr L* j1-f j I1!6 2 0曰甌 勺勺勺勺勺勺：bcau孔bJ 二 di 二，-n I二_ 丄二H二4 0 7 b d产严b階至至至至至至 到到到到到 H_ibibscic -53aabbDD pduduHO4HduduB齬iiStepl :运行程序，屏幕显示菜单。Step2：运行功能选择。Casel:输入“1”选择菜单项1，进入图的创建操作。1.3根据屏幕提示，创建有向网。1.4屏幕显示网信息。Case2：输入“ 2”，选择菜单项2，进入求各点之间最短距离的操作。 屏幕显示求得各点之间的最短的距离和路径。Case3:输入“ 3”，选择菜单项3，结束程序运行。4、思考题阅读源程序，回答下列问题。1）有向图的单源点问题与无向图的单源点问题求解有何异同？答：将无向图中一条无向边看作方向任意的一条有向边，得到一有向图集合，从而可以将路径、循环等