最短最優(yōu)路徑算法附程序代碼

實驗報告一一題目要求輸入N(N<10)個城市，每兩個城市之間有對應(yīng)的距離和費用(可以不能到達)，要求實現(xiàn)如下程序：給出任意兩個城市之間的最短距離，及其到達方式；給出任意兩個城市之間的最小費用，及其到達方式；權(quán)衡距離和費用，給出任意兩個城市之間的最優(yōu)路徑，及其到達方式；PS：1,距離矩陣和費用矩陣由同學(xué)自己給出；題c)的最優(yōu)路徑由自己定義。算法設(shè)計：欲求得每一對頂點之間的最短路徑，解決這一問題的辦法是采用弗洛伊德算法。弗洛伊德算法仍從圖的帶權(quán)鄰接矩陣出發(fā)，其主要思想是：設(shè)集合S的初始狀態(tài)為空集合，然后依次向集合S中加入頂點V0,V1,V2，…，Vn-1，每次加入一個頂點，我們用二維數(shù)組D保存每一對頂點之間的最短路徑的長度，其中，D[i][j]存放從頂點Vi到Vj的最短路徑的長度。在算法執(zhí)行中，D[i][j]被定義為：從Vi到Vj的中間只經(jīng)過S中的頂點的所有可能的路徑中最短路徑的長度(如果從Vi到Vj中間只經(jīng)過S中的頂點當前沒有路徑相通，那么d[i][j]為一個大值MaxNum)。即d[i][j]中保存的是從Vi到Vj的“當前最短路徑”的長度。每次加入一個新的頂點，Vi和Vj之間可能有新的路徑產(chǎn)生，將它和已經(jīng)得到的從Vi到Vj的最短路徑相比較，d[i][j]的值可能需要不斷修正，當S=V時，d[i][j]的值就是從Vi到Vj的最短路徑。因為初始狀態(tài)下集合S為空集合，所以初始化D[i][j]=A[i][j](A[i][j]是圖的鄰接矩陣)的值是從Vi直接鄰接到Vj，中間不經(jīng)過任何頂點的最短路徑。當S中增加了頂點V0,那么D(0)[i][j]的值應(yīng)該是從Vi到Vj，中間只允許經(jīng)過v0的當前最短路徑的長度。為了做到這一點，只需對D(0)[i][j]作如下修改：D(0)[i][j]=min{D[i][j],D[i][0]+D[0][j]}一般情況下，如果D(k-1)[i][j]是從Vi到Vj，中間只允許經(jīng)過{V0,V1,V2，…，Vk-1}的當前最短路徑的長度，那么，當S中加進了Vk，則應(yīng)該對D進行修改如下：D(k)[i][j]=min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}概要設(shè)計：數(shù)據(jù)結(jié)構(gòu)二維數(shù)組來表示鄰接矩陣，數(shù)組中存儲元素表示鄰接點之間的距離，或費用。抽象數(shù)據(jù)類型有向圖函數(shù)接口Voidmain()主函數(shù)VoidDispmat()輸出鄰接矩陣函數(shù)VoidFloyed()計算最短路徑函數(shù)VoidDispath()輸出最短路徑函數(shù)詳細設(shè)記Main函數(shù)的流程圖如下：DispMat(MGraphg)函數(shù)流程圖如下:Dispath(doubleA[][MAXV],intpath[][MAXV],intn)函數(shù)流程圖如下:開始i=0,j=0printf("從％￡|printf("從％￡|到％￡|的路徑為:",i,j);printf("%d,",i);ppath(path,i,j);printf("%d",j);printf("\路徑長度為:％.2lf\n”,(double)A[i][j]);N 結(jié)束Floyd（MGraphg）函數(shù)流程圖如下:開始i=0,j=0YNA[i][j]>A[i][k]+Yprintf("\n輸出最短路徑:\n");Dispath(A,path,n);〃輸出最短路徑A[i][j]=A[i][k]+A[k][j];path[i][j]=k;開始i=0,j=0YNA[i][j]>A[i][k]+Yprintf("\n輸出最短路徑:\n");Dispath(A,path,n);〃輸出最短路徑A[i][j]=A[i][k]+A[k][j];path[i][j]=k;path[i][j]=-1;結(jié)束調(diào)試分析與心得體會本次程序開始之初，我首先構(gòu)思了大致結(jié)構(gòu)，考慮到需要多個函數(shù)來完成功能，我從各個子函數(shù)開始，編寫各個子函數(shù)。本次設(shè)計的重點是FLOYD算法。計算最優(yōu)路徑的核心思想是FLOYD算法。我花費了大量的時間編寫FLOYD函數(shù)，并進行多次修改才可以正常運行。從最初程序的短短幾十行到本次程序的一百多行，此次設(shè)計讓我收獲頗多。函數(shù)編寫過程中遇到多處錯誤，經(jīng)過思考和與同學(xué)探討最終正確完成了程序。用戶操作說明及運行結(jié)果顯示首先請輸入城市個數(shù)和弧數(shù)（整型數(shù)據(jù)）：510。下面計算任意兩個城市之間的最短距離：請輸入距離矩陣的邊（以"-1-1-1"作為結(jié)束標志）:每組數(shù)據(jù)輸入兩個鄰接點和其間距離，數(shù)據(jù)間以空格隔開。Eg.1350412218-1-1-1

10.下面計算任意兩個城市之間的最短距離：請輸入距離矩陣的邊〈以"-1-1-1'-作為結(jié)束標志X512181-1-1COCOCO12.00CO8.005.00CO8.00COcoco5.00cococo.00COCOCOCO040000

-00

-M-■■

185

度度度

-K040000

-00

-M-■■

185

度度度

-K-K-K

路路路1110000--■_b0J811度度度-K-K-K路路路ill000000---30511度度度-K-K-K路路路111路徑長度為■麗-為為徑為為為iWi為為為為為為徑為信路路路徑路Itwl路路Itwl路路路徑路路路鐸踏踏有有有路有略略略有有略略略有有略略略有路有有有四短的SK悠籥唇的的^E的的的的皤mK:K僻曰職。1:;4I::;4I::;dI:::dI:::d也劍劍劍劍劍劍劍劍劍劍劍劍劍劍劍劍劍劍510123401234012340123401234下面計算任意兩個城市之間的最小費用：請輸入費用矩陣的邊（以"-1-1-1"作為結(jié)束標志）：每組數(shù)據(jù)輸入兩個鄰接點和其間費用，數(shù)據(jù)間以空格隔開。Eg.237042136-1-1-1

路徑長度為：2.朋路徑長度為：4,風有向圖G的鄰接矩陣:boCOCOCO2.00:：■：:路徑長度為：2.朋路徑長度為：4,風有向圖G的鄰接矩陣:boCOCOCO2.00:：■：:：■COCO6.00cobe：'COCO7.00coco6.007.00CC-cc-2.00cocococoe*D:\0\Debug\0.exe▼000000---2671度度度路路路000--023-116度度度路路路000--0117.度度度-K-KW&S.路路路4IJ00JJ43JJ1213331233322212333111請輸入戚用矩陣的邊〈以”T-1T”作為結(jié)束標志〉:23704213611-1-10JJ4JJ0:為徑為為為iWi為為為為為為徑為為寰路路路徑路ItWl路路路路路徑路路路祥路路有有有路有路路路有有路路路有有路路路有路有有有路短的函0JJ4JJ0:為徑為為為iWi為為為為為為徑為為寰路路路徑路ItWl路路路路路徑路路路祥路路有有有路有路路路有有路路路有有路路路有路有有有路短的函K您郡蓄的的3K胡的的^^的的蓄函燧您鼎最01234SI1234SI1234ISI1234SI1234而到到到到到到到到到到到到到到到到到到到到到到到到到H-U0000011111222223333344444路徑長度為壯，施請輸入權(quán)值a0,b0（a0>0&&b0>0&&a0+b0=1a0和b0都為小數(shù)）：Eg.0.250.75。土*D:\0\Debug\0.eze*□|x|請輸入權(quán)值胡請輸入權(quán)值胡>b0<a0>0.250.75lhr：.iI季的11?*_|-Jh.j畢r1.3L口|_ln興才節(jié)KJ心&&b0>0&&a0+b0=l糖和h。都為小數(shù)）：DCOCOCO4.50jco24577.255_75coCO:=：124577.25co8197.00CO:=：15.758197.00coco.50cocococo路徑長度為才■晌路筐長度為路徑長度為政跛K盛格長度為瀉K111度度度

-K-K-K

路路路57579-■4^581

度度度

-K-K-K

路路路121路徑長度為=4.弱:為為徑為為為iWi為為為iWi為為為徑為為卷路路路徑路！^W路路！^^路路路徑路路路徑路路有有有路有路路路有有路路路有有路路路有路有有有路短的misK曲唇的的3.K籥的的俱瘵籥的的裔3KK郡出至至至至至至至至至至多多多多多手手手手手手手多多多Hn00000111112222233333444440123401234012340123401234請輸入權(quán)值a0,b0<a0>0&&b0>0&&a0+b0=lM和成都為小數(shù)》:八.附件附有源程序如下：#include<stdio.h>#defineINF32767typedefintInfoType;#defineMAXV100 〃最大頂點個數(shù)〃以下定義鄰接矩陣類型typedefstruct{intno; 〃頂點編號InfoTypeinfo; 〃頂點其他信息，這里用于存放邊的權(quán)值}VertexType; 〃頂點類型typedefstruct〃圖的定義{doubleedges[MAXV][MAXV];〃鄰接矩陣intn,e; 〃頂點數(shù)，弧數(shù)VertexTypevexs[MAXV];〃存放頂點信息}MGraph;〃圖的鄰接矩陣類型}MGraph;voidDispMat(MGraphg)〃輸出鄰接矩陣G{inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++)if(g.edges[i][j]==INF)printf("%3s”,"8”);elseprintf("%.2lf",g.edges[i][j]);printf("\n");}}voidppath(intpath[][MAXV],inti,intj){intk;k=path[i][j];if(k==-1)return;ppath(path,i,k);printf("%d,”,k);ppath(path,k,j);}voidDispath(doubleA[][MAXV],intpath[][MAXV],intn){inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++)if(A[i][j]==INF){if(i!=j)printf("從％d到％d沒有路徑\n",i,j);}else{printf("M%d到％d的路徑為:",i,j);printf("%d,",i);ppath(path,i,j);printf("%d”,j);printf("\t路徑長度為:％.2lf\n”,(double)A[i][j]);}}〃采用弗洛伊德算法求每對頂點之間的最短路徑voidFloyd(MGraphg){doubleA[MAXV][MAXV];intpath[MAXV][MAXV];inti,j,k,n=g.n;for(i=0;i<n;i++)for(j=0;j<n;j++){A[i][j]=g.edges[i][j];path[i][j]=-1;}for(k=0;k<n;k++){for(i=0;i<n;i++)for(j=0;j<n;j++)if(A[i][j]>A[i][k]+A[k][j]){A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}}printf("\n輸出最短路徑:\n");Dispath(A,path,n);//輸出最短路徑}voidmain(){inti,j,u=0,m,k,num;MGraphg;intA[MAXV][MAXV],B[MAXV][MAXV];doubleC[MAXV][MAXV],a0,b0;for(k=0;k<MAXV;k++)for(m=0;m<MAXV;m++)A[k][m]=INF;for(k=0;k<MAXV;k++)for(m=0;m<MAXV;m++)B[k][m]=INF;for(k=0;k<MAXV;k++)for(m=0;m<MAXV;m++)C[k][m]=INF;printf("請輸入城市個數(shù)和弧數(shù)：\n");scanf("%d%d”,&g.n,&g.e);printf("1.下面計算任意兩個城市之間的最短距離：\n");printf(-請輸入距離矩陣的邊(以\"-1-1-1\"作為結(jié)束標志):\n");while(1){scanf("%d”,&i);scanf("%d”,&j);scanf("%d”,&num);if(i==-1&&j==-1&&num==-1)break;if((i<0||i>=g.n)||(j<0||j>=g.n)){printf("輸入錯誤!”)；}A[i][j]=A[j][i]=num;}for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g.edges[i][j]=A[i][j];printf("\n");printf(”有向圖G的鄰接矩陣:\n");DispMat(g);Floyd(g);printf("\n");printf("2.下面計算任意兩個城市之間的最小費用：\n");printf("請輸入費用矩陣的邊(以\"-1-1-1\"作為結(jié)束標志):\n");while(1){scanf("%d”,&i);scanf("%d”,&j);scanf("%d”,&num);if(i==-1&&j==-1&&num==-1)break;