《GIS工程與應用》課程實驗報告項目名稱： 最佳路徑小組成員：學生學號： 2009070,200920090指導教師：完成日期： 2013-1-2一、 背景最短最優化路徑問題是一個重要的問題，也是地理信息系統、通信、物流管理、計算機科學等領域的研究熱點。目前，國內外學者對此問題進行了大量的研究，在這些研究成果中，絕大部分都是基于靜態網絡的，也就是說路徑尋優中網絡弧段的權值是固定不變的，然而實際生活中的很多問題，其網絡弧段的權值是隨時間變化的，比如道路交通網絡和通信網絡。本文主要基于地理信息系統GIS，對校園網絡中的兩點之間的最短最優化路徑進行實現。二、 意義近幾十年來，靜態網絡最短路徑算法已經得到充足的發展，但在現實生活中很多應用領域如110報警、119火警、醫療救護等，都需要盡快獲得到達目得地的最快路徑，以便處理突發事故。相對于靜態最短路徑算法而言，基于GIS的時變最短路徑成果還很少，時變最短路徑算法能與全球定位系統、GIS和ITS技結合在一起，綜合每條道路不同時段的不同路況，找出最短最優的路徑。本文就最簡單最基本的校園兩點之間的最短最優化路徑，做了幾個簡單的功能實現。三、 系統功能輸入N（N<10）個校園出發點，每兩個地點之間有對應的距離和費時（可以不能到達），要求實現如下程序：a） 給出任意兩個校園出發點之間的最短距離，及其到達方式；b） 給出任意兩個校園出發點之間的最少用時，及其到達方式；c） 權衡距離和費用，給出任意兩個城市之間的最優路徑，及其到達方式；PS：1,距離矩陣和費用矩陣由同學自己給出；題c）的最優路徑由自己定義。四、 算法設計欲求得每一對頂點之間的最短路徑，解決這一問題的辦法是采用弗洛伊德算法。弗洛伊德算法仍從圖的帶權鄰接矩陣出發，其主要思想是：設集合S的初始狀態為空集合，然后依次向集合S中加入頂點V0,V1,V2，…，Vn-1，每次加入一個頂點，我們用二維數組D保存每一對頂點之間的最短路徑的長度，其中，D[i][j]存放從頂點Vi到Vj的最短路徑的長度。在算法執行中，D[i][j]被定義為：從Vi到Vj的中間只經過S中的頂點的所有可能的路徑中最短路徑的長度（如果從Vi到Vj中間只經過S中的頂點當前沒有路徑相通，那么d[i][j]為一個大值MaxNum）。即d[i][j]中保存的是從Vi到Vj的“當前最短路徑”的長度。每次加入一個新的頂點，Vi和Vj之間可能有新的路徑產生，將它和已經得到的從Vi到Vj的最短路徑相比較，d[i][j]的值可能需要不斷修正，當S=V時，d[i][j]的值就是從Vi到Vj的最短路徑。因為初始狀態下集合S為空集合，所以初始化D[i][j]=A[i][j]（A[i][j]是圖的鄰接矩陣）的值是從Vi直接鄰接到Vj，中間不經過任何頂點的最短路徑。當S中增加了頂點V0,那么D（0）[i][j]的值應該是從Vi到Vj，中間只允許經過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，中間只允許經過{V0,V1,V2，…，Vk-1}的當前最短路徑的長度，那么，當S中加進了Vk，則應該對D進行修改如下:D(k)[i][j]=min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}概要設計數據結構二維數組來表示鄰接矩陣，數組中存儲元素表示鄰接點之間的距離，或費時。抽象數據類型有向圖函數接口Voidmain()主函數VoidDispmat()輸出鄰接矩陣函數VoidFloyed()計算最短路徑函數VoidDispath()輸出最短路徑函數詳細設計Main函數的流程圖如下：DispMat(MGraphg)函數流程圖如下:開始Dispath(doubleA[][MAXV],intpath[][MAXV],intn)函數流程圖如下:printf("從％￡|到％￡|的路徑為:",i,j);printf("%d,",i);ppath(path,i,j);printf("%d",j);printf("\路徑長度為:％.2lf\n”,(double)A[i][j]);N 結束Floyd(MGraphg)函數流程圖如下:j++K=0,i=0,j=0k<nYi<ni++Nj<nA[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;k++j++結束運行結果顯示首先請輸入校園出發點個數和弧數(整型數據):48。1.下面計算任意兩個出發點之間的最短距離：

『P\G]5二程與應用偈佳咨?貝司小,易侄楚登點能請輸成校園出發點個數和弧數：481-7■■面計算任意兩個出發點之間的最短距商:請輸或距離矩陣的邊《以-1-1-r-作為2吉束標志）:23.535.732.5-1-1-1羹向圖G的鄰接矩陣二cocoQP5.70cocp3.5aco^63.50QP2.5SrtS.7^QO2.5JS3_w-K--K--K--K-

25057".一」.一F"」.一V亶度亶度度度度亶亶度亶亶度亶度度<><-:>>嘿>><>>始>>嘍>lliss881各各各k口k口k口k口k口k口k口k口k口k口』有D-!=!iEH=!iEH=!iEH=!iEH=!iEH=!iEH=!iEH=!,EH=!,EH=!,133022231^—^.i^—^.—^J.—^—^.I^J.ii^J.—^—T—T—F-v—VI^J.■■^r\^r\^r\^rx^rx^rx^rx^T\^r\^r\^r\^r\^r\^r\^r\^r\iiiisiiii□-4D-4D-4D-4CHdiCHdiCHdiCHdiCHd,CHd,CHd,CHd,CHd,CHd,CHd,CHd,CHd,—.3J-Inn.Inn.—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn12391239123^123□^0600111.1222233332漕歌新擂蹌罰和H%為結束標志）:rrr2.下面計算任意兩個校園出發點之間的最少用時:

'Dl\G]5工程與應用偈佳曹徑L口ebu易蛙珞曉.exe"原膏艾葺青瞿描蓊M睥陣為結束標.128.57.0有向圖G的鄰接矩陣二COCOCO?.00cocpg.saco^6S.50QP5.00QO5.S303紈弱12.as7.0017.as8.5013.5012.008.50la.Sfti：紈弱12.as7.0017.as8.5013.5012.008.50la.Sfti：.907.9013.50E-德V—V—V—V—V—V—V亶度亶度度度度度亶度度亶度度亶度-fe-fe-fe-fe-fe-fe-fe-fe-fe-fe-fe-fe-fe-fe-fe-feislllllsnTKnTKnxu^nTKHinTKnTKnx^nTKnTKnxu^nTKnTKTKnTKnTK322223133022^-11112222333V—V—V—V—V—F"V—F"V—F"V—F"T—T—F"vl^iT—F"vl^iT—vi^iV■■^r\^r\^r\^r\^rx^rx^rx^rx^T\^r\^r\^r\^r\^r\^r\^r\iiiisiiil□-4D-4D-4D-4D-4CHdiCHdiCHdiCHdiCHd,CHd,CHd,CHd,CHd,CHd,CHd,CHd,—.3J-—.3J-Inn.Inn.—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn—rtn12391239123^123^^0000111.122223333^1230123M-12391233-權黃距離和用時，給出任意兩個發出點之間的最偽路帶及其到達方請輸入權■■值糖，h永糖用&&bB>0&&a0+b?-l弱和h(3都為小數》：rrr權衡距離和時間，給出任意兩個校園出發點之間的最優路徑，及其到達方式。此時定義最

短路徑為兩鄰接點之間的距離乘以a0與兩鄰接點之間的費用乘以b0的

和 .■"D05工程與應用偈佳路曲DebugW佳路經，*30.713.2217.8610.866.6117.8614.007.0011.2510.867.008.504.256.6111.254.258.50習..■■■■習..■■■■30.713.2217.8610.866.6117.8614.007.0011.2510.867.008.504.256.6111.254.258.50習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■習..■■■■

度度度度度度度度度度度度度度度度

-K-K-K-K-K-K-K-K-K-K-fc-fc-fc-fc-fc-fc

k口k口k口k口k口k口k口k口k口k口膏膏膏膏膏』■:■:□

□-4n-4n-4n-4n-4n-4n-4n-4n-4n-4n-4n-4n-4n-4n-4□-!=!,133022222333LM—VLM—VLM—VLM—VLM—VLM—VLM—VLM—VLM—VLM—VLM—VLM—VLM—VLM—VLM—VLM—V71-z,71-z,71-z,71-z,71-z,71-z,71-z,71-z,71-z,71-z,71-z,71-z,71-z,方g育方g育占廿占廿占廿占廿占廿占廿占廿占度耳宣占廿占廿占廿□Hz!,End,End,End,EHd,CH4CH4CH4CH4CH4CH4CH4CH4CH4CH4CH4CH4-R.-IT"=.-17~=.-17~=.-17~=.-17~=.-17~=.-17~=.-17~=.-17~=.-17~=.-17~=.-17~=.-17~=.-17~=.-17~=.-17"=.J^.1■—&u—&u—&u—&u—&u—&u—&u—&u—&u—&u—Ou—Ou—Ou—Ou—Ou—Ou0123012301230123也王至至至至至至至至至至至至至至至UU0000111122223333隊隊隊隊隊隊隊隊隊從從從從從從口用時，紿出任意兩個發出點之間的最Ea0,b0<a0>0&&b0>0&&a0+b0=la0有向圖G的鄰接矩陣二CO8CO6.61COCO?.00COCO7.00004.256.61CO4.258請輸入權值a8,b0<a0>0&&b0>0&&a0+bB=la0Snb0§P7ndW>請輸入權值a8,b0<a0>0rrr六.附件附有源程序如下：#include<stdio.h>#defineINF32767typedefintInfoType;#defineMAXV100 〃最大頂點個數〃以下定義鄰接矩陣類型typedefstruct{intno; 〃頂點編號InfoTypeinfo; 〃頂點其他信息，這里用于存放邊的權值}VertexType; 〃頂點類型typedefstruct 〃圖的定義{doubleedges[MAXV][MAXV];〃鄰接矩陣intn,e; 〃頂點數，弧數VertexTypevexs[MAXV];〃存放頂點信息}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(doubleDistance[][MAXV],intpath[][MAXV],intn){inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++)if(Distance[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)Distance[i][j]);}}〃采用弗洛伊德算法求每對頂點之間的最短路徑voidFloyd(MGraphg){doubleDistance[MAXV][MAXV];intpath[MAXV][MAXV];inti,j,k,n=g.n;for(i=0;i<n;i++)for(j=0;j<n;j++){Distance[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(Distance[i][j]>Distance[i][k]+Distance[k][j]){Distance[i][j]=Distance[i][k]+Distance[k][j];path[i][j]=k;}}printf("\n輸出最短路徑:\n");Dispath(Distance,path,n);//輸出最短路徑}voidmain(){inti,j,u=0,m,k;MGraphg;doubleDistance[MAXV][MAXV],Time[MAXV][MAXV];doubleC[MAXV][MAXV],a0,b0,num;for(k=0;k<MAXV;k++)for(m=0;m<MAXV;m++)Distance[k][m]=INF;for(k=0;k<MAXV;k++)Time[k][m]=INF;for(k=0;k<MAXV;k++)for(m=0;m<MAXV;m++)C[k][m]=INF;printf(-請輸入校園出發點個數和弧數：\n");scanf("%d%d”,&g.n,&g.e);printf("1.下面計算任意兩個出發點之間的最短距離：\n");printf(-請輸入距離矩陣的邊(以\"-1-1-1\"作為結束標志):\n");while(1){scanf("%d”,&i);scanf("%d”,&j);scanf("%lf”,&num);if(i==-1&&j==-1&&num==-1)break;if((i<0||i>=g.n)||(j<0||j>=g.n)){printf("輸入錯誤!”)；}Distance[i][j]=Distance[j][i]=num;}for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g.edges[i][j]=Distance[i][j];printf("\n");printf(”有向圖G的鄰接矩陣:\n");DispMat(g);Floyd(g);printf("\n");printf("2.下面計算任意兩個出發點之間的費用：\n");printf("請輸入費用矩陣的邊(以\"-1-1-1\"作