最短路径实验报告

实验最短路径

姓名：班级：学号：试验时间：一、从某个源点到其余各顶点的最短路径1、问题描述本实验实现dijkstia算法。图存储采用了数组存储结构。图类的定义为第9.1.1节图类的修改，仅保留了与本程序有关的成员函数，增添了一个求单源点最短路径的成员函数。2、算法设计源程序：template<classT>voidMGraph<T>::ShoilestPath_DIJ(mtvO.PatliMatiix_1&P,ShoitPathTable&D)〃用Dijkstra算法求有向网的vO顶点到其余顶点v的最短路径P[v]及带权长度//D[v]o若P[v][w]为true,则w是从vO到v当前求得最短路径上的顶点。//fiiial[v]为true当且仅当vGS,即已经求得从vO到v的最短路径{mtv,w,i,j,nuii;boolfinal[MAX_\TRTEX_NUM];//辅助矩阵，为真表示该顶点到vO的最短距离己求出，初值为假for(v=O;v<mgiaph.vexnum;v++){final[v]=false;//设初值D[v]=mgiaph.arcs[\O][v].adj;〃D□存放vO到v的最短距离，初值为vO到v的直接距离fbr(w=0;w<mgraph.vexiium;w++)//设空路径{P[v][w]=false;}if(D[v]<infiiuty)//vO到v有直接路径{_P[v][vO]=P[v][v]=tme;//―维数组p[v]口表示源点vO到v最短路径通过的顶点}}D[vO]=0;//vO到vO距离为0final[\O]=true;〃vO顶点并入S集for(i=1;i<mgraph.vexiium;i++)〃其余G.vexiium-1个顶点〃开始主循环，每次求得vO到某个顶点v的最短路径，并将v并入S集min=nifuuty；//当前所知离vO顶点的最近距离，设初值为8fbr(w=O;w<mgraph.vexiium;w++)//对所有顶点检查{if(!fuial[w]&&D[w]<inui)〃在S集之外的顶点中找离vO最近的顶点，并将其赋给v,距离赋给min{v=w;niin=D[w];}final[v]=tme;//离vO最近的v并入S集fbr(w=O;w<mgraph.vexiium;w++)//根据新并入的顶点，更新不在S集的顶点到vO的距离和路径数组{ift!fuial[w]&&nuii<mfuuty&&mgiapli.aics[v][w].adj<uifuuty&&(mui+mgiapli.aics[v][w].adj<D[w]))〃w不属于S集且vO—v—w的距离<目前vO—w的距离{D[w]=min+mgraph.aics[v][w].adj;//更新D[w]for(j=0;j<mgiapli.vexiiumj++)//修改P[w],vO到w经过的顶点包括vO到v经过的顶点再加上顶点W{P[W]|J]=P[V]|J]；}P[w][w]=true;}}}3、运行与测试程序运行如图所示。

■・G:\学习谓湊结构实\9.4\DLI\Debug\SPath_DU.exe-)顶构个结各储余组到警(源图个创^择择人人兀人人人人人、•・•选选占小123主冃青主冃主冃青主冃主冃青主冃主冃青5■・G:\学习谓湊结构实\9.4\DLI\Debug\SPath_DU.exe-)顶构个结各储余组到警(源图个创^择择人人兀人人人人人、•・•选选占小123主冃青主冃主冃青主冃主冃青主冃主冃青5y顶235411:bcddbC为8aacbee辟有弧邻85,d占竄占I:占篇諭苓bC终终终终终终网理枫点%b竄占第占竄向加的顶.:起起起起起起有衣项网的网顶弧弧弧弧弧弧弧b需要向个浅25鍔网个向的-coCOcocoCOco3-弓111111a01010单x创建图（数组匠储结构）

求鲁个源盖到苴余各个顶点的最短路径

變单项：2

径数组pliHjl^n下二0000801000001002到各顶点的最短路径长度为;a~b:2a-c：3a-d:6Stepl：运行程序，屏幕显示菜单。Step2：运行功能选择。Casel：输入T,选择菜单项1,进入图的创建操作。1.1根据屏幕提示，创建有向网。1.2屏幕显示网信息。Case2：输入“2”，选择菜单项2,进入求源点到其他各点的距离操作。屏幕显示求得源点到其他各点的距离和路径数组。Case3:输入“3”，选择菜单项3,结束程序运行。二、每一对顶点之间的最短路径1、问题描述本程序用于验证flovd算法。图采用了邻接表存储。图类的定义为第9.1.2节图类的修改，仅保留了与本程序用到的基本操作，増添了拓扑排序成员函数。2、算法设计源程序：template<classT>voidMGraph<T>::ShortestPatli_FLOYD(PatliMatrix_2&RDistaiicMatiix&D)//用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w]//若P[v][w][u]为TRUE,则u是从v到w当前求得最短路径上的顶点。{intu,v,wj;fbr(v=0;v<mgraph.vexiium;v++)〃各对结点之间初始已知路径及距离{for(w=0;w<mgraph.vexiiuin;w++){D[v][w]=mgraplLaics[v][w].adj;//顶点v到顶点w的直接距离fbr(u=0;u<mgiaph.vexnum:u++){P[v][w][u]=false;//路径矩阵初值}if(D[v][w]<mfinity)〃从V到w有直接路径{P[v][w][v]=P[v][w][w]=tine;〃由v到w的路径经过v和w两点}}}for(u=0;u<mgraph.vexiium;u-H-){fbr(v=O;v<mgraph.vexnum;v-H-){fbr(w=O;w<mgraph.vexiium;w++){if(D[v][u]+D[u][w]<D[v][w]){D[v][w]=D[v][u]+D[u][w];//更新最短距离fbr(i=0:i<mgraph.vexiium;i++)P[V][W][1]=P[v][u][l]||P[u][w][i]；}3、运行与测试a°G:\学习谓濡结构卖跪\g_^\9・4\FLOYD\Debug\：SP£th_FLO¥D・exy兴径1路组之7Xrl无向网CL》05461132菜图对•建一岀操畐貫口二二一亍<•「迤衆aaaasa捌I••-II点123主冃主冃土冃主冃主冃主冃主冃主冃主冃主冃M两IIbacaCabacbbc喙唆1种点ab占養占竄向的11的顶：，起起起起起星••网的网顶弧弧弧弧弧弧G作向要向个WWWb4电一一一一一£a...•...xaaaaaa^t>-■<0数网A.—向的有弧壬网邻X傕—路91S0单存间组之7\-11翼2

8菜图对作建一岀操创每退叠-1230离离离离离离一n--n--n=n--n--n-ss3SSs馬一CH=Ee=s_®ES_-20曇5SBB取」」二-J二」「-」n-07bcacabr.到到到到到aa■■■■rj■过经经经经经经bacab阵到到到到到到aabbcc由由由由由由Stepl：运行程序，屏幕显示菜单。Step2：运行功能选择。Casel：输入“1”，选择菜单项1,进入图的创建操作。1.3根据屏幕提示，创建有向网。1.4屏幕显示网信息。Case2：输入“2”，选择菜单项2,进入求各点之间最短距离的操作。屏幕显示求得各点之间的最短的距离和路径。Case3:输入“3”，选择菜单项3,结束程序运行。4、思考题阅读源程序，回答下列问题。1）有向图的单源点问题与无向图的单源点问题求解有何异同？答：将无向图中一条无向边看作方向任意的一条有向边，得到一有