數(shù)據(jù)結構與算法課程設計-求解最短路徑

綜合實驗任務書姓名學號班級課程名稱數(shù)據(jù)結構與算法課程性質專業(yè)必修課設計時間2008年12月15日——2009年1月2日設計名稱求解最短路徑設計要求能夠完成以下功能：1)建立圖2)實現(xiàn)Dijkstra單源點最短路徑算法3)實現(xiàn)Floyd算法，實現(xiàn)求解每對結點之間的最短路徑問題4)有錯誤提示功能，例如非法輸入時，會有報錯。設計思路與設計過程根據(jù)系統(tǒng)功能要求，可以將問題解決分為以下步驟：（1）分析問題實質；（2）抽取問題實質，進行抽象；（3）確定數(shù)據(jù)結構；（4）選擇合適的算法，進行算法設計；（5）完成系統(tǒng)的應用模塊；（6）功能調試；（7）修改不完善的功能，增強程序健壯性；（8）根據(jù)實際添加所需功能；計劃與進度由簡單到復雜，爭取15天左右完成任課教師意見說明

設計名稱：求解最短路徑 日期：2009年1月2日設計內容：設計一個系統(tǒng)，實現(xiàn)以下功能：1：建立圖2：實現(xiàn)Dijkstra單源點最短路徑算法3：實現(xiàn)Floyd算法，實現(xiàn)求解每對結點之間的最短路徑問題4：退出系統(tǒng)設計目的與要求：（1）達到理論與實際應用相結合，能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內部表示出來，并培養(yǎng)良好的程序設計技能。（2）在實踐中認識為什么要學習數(shù)據(jù)結構，掌握數(shù)據(jù)結構、程序設計語言程序設計技術、之間的關系。通過設計，在數(shù)據(jù)結構的邏輯特性和物理表示、數(shù)據(jù)結構的選擇應用、算法的設計及其實現(xiàn)等方面加深對課程基本內容的理解和綜合運用。設計環(huán)境或器材、原理與說明：MicrosoftVisualC++6.0設計過程（步驟）或程序代碼：#include<stdio.h>#include<iostream.h>#defineMAX10000#defineMAXLEN20#defineMAX_VERTEX_NUM20typedefstruct{ charvexs[MAX_VERTEX_NUM];//頂點表 intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//鄰接矩陣 intvexnum,arcnum;//圖的頂點數(shù)和弧數(shù)}MGRAPH;MGRAPHcreate_mgraph()//建立有向圖的鄰接矩陣結構{inti,j,k,h; MGRAPHmg; printf("\n\n輸入頂點數(shù)和邊數(shù)(用逗號隔開):"); while(1)//判斷輸入是否合法 { if(scanf("%d,%d",&i,&j)==2&&getchar()=='\n'&&i<MAX_VERTEX_NUM&&j<MAX_VERTEX_NUM)break; else { while(getchar()!='\n'); cout<<"輸入不合法！"<<endl; printf("請重新輸入頂點數(shù)和邊數(shù)(用逗號隔開):"); } } mg.vexnum=i;//存放頂點數(shù)在mg.vexnum中 mg.arcnum=j;//存放邊點數(shù)在mg.arcnum中 fflush(stdin);//清空緩沖區(qū) for(i=0;i<mg.vexnum;i++) { printf("輸入頂點%d的值:",i+1);//輸入頂點的值 while(1)//判斷選擇是否合法 { if(scanf("%d",&mg.vexs[i])==1&&getchar()=='\n')break; else { while(getchar()!='\n'); cout<<"輸入不合法！"<<endl; printf("請重新輸入頂點%d的值:",i+1); } }fflush(stdin); }for(i=0;i<mg.vexnum;i++)//鄰接矩陣初始化 for(j=0;j<mg.vexnum;j++) mg.arcs[i][j]=MAX; for(k=1;k<=mg.arcnum;k++) { printf("輸入第%d條邊的起始頂點和終止頂點(用逗號隔開):",k); while(1)//輸入弧的起始頂點和終止頂點，并判斷輸入是否合法 { /* scanf("%d,%d",&i,&j)的作用：判斷是否成功輸入 如果i和j都被成功讀入，那么scanf的返回值就是2 如果只有i被成功讀入，返回值為1 如果i和j都未被成功讀入，返回值為0 */ if(scanf("%d,%d",&i,&j)==2&&getchar()=='\n'&&i>0&&i<=mg.vexnum&&j>0&&j<=mg.vexnum)break; else { while(getchar()!='\n'); cout<<"輸入不合法！"<<endl; printf("請重新輸入起始頂點和終止頂點(用逗號隔開):"); } }fflush(stdin);while(i<1||i>mg.vexnum||j<1||j>mg.vexnum) { printf("輸入錯，重新輸入:"); scanf("%d,%d",&i,&j); } printf("輸入此邊權值:");//輸入弧上之權值 while(1)//判斷輸入是否合法 { if(scanf("%d",&h)==1&&getchar()=='\n')break; else { while(getchar()!='\n'); cout<<"輸入不合法！"<<endl; printf("請重新輸入此邊權值:"); } }mg.arcs[i-1][j-1]=h; } returnmg;}voidDijkstra(MGRAPHmg){intcost[MAXLEN][MAXLEN];intpath[MAXLEN],flag[MAXLEN];intdist[MAXLEN];inti,j,n,v0,min,u,back=0; printf("\n求有向圖單源點最短路徑\n"); printf("\n\n起始頂點為:");//有向圖中頂點的編號從1編起 while(1)//判斷選擇是否合法 { if(scanf("%d",&v0)==1&&getchar()=='\n'&&v0<=mg.vexnum)break; else { while(getchar()!='\n'); cout<<"輸入不合法！"<<endl; printf("請重新輸入起始點："); } }printf("\n\n");v0--;n=mg.vexnum;for(i=0;i<n;i++)//cost矩陣初始化 { for(j=0;j<n;j++)cost[i][j]=mg.arcs[i][j];cost[i][i]=0; }for(i=0;i<n;i++) { dist[i]=cost[v0][i];//dist數(shù)組初始化if(dist[i]<MAX&&dist[i]>0)//path數(shù)組初始化path[i]=v0; }for(i=0;i<n;i++)//s數(shù)組初始化 flag[i]=0; flag[v0]=1;for(i=0;i<n;i++)//按最短路徑遞增算法計算{ min=MAX;u=v0;for(j=0;j<n;j++) if(flag[j]==0&&dist[j]<min) { min=dist[j];u=j; }flag[u]=1;//u頂點是求得最短路徑的頂點編號for(j=0;j<n;j++) if(flag[j]==0&&dist[u]+cost[u][j]<dist[j])//調整dist { dist[j]=dist[u]+cost[u][j];path[j]=u; }//path記錄了路徑經(jīng)過的頂點 } printf("最短路徑\t\t\t\t\t路徑值\n");for(i=0;i<n;i++)//打印結果if(flag[i]==1) //有路徑 { back=0; u=i;while(u!=v0) { printf("v%d<-",u+1);u=path[u]; back++; } printf("v%d",u+1); for(intc=46;c>0;c--) printf(""); for(;back>0;back--)//調整輸出格式 printf("\b\b\b\b");printf("d=%d\n",dist[i]);} elseprintf("v%d<-v%d\t\t\t\t\t\td=MAX\n",i+1,v0+1);//無路徑printf("\n\n");} voidFloyd(MGRAPHmg)//求每對結點之間的最短路徑{intCost[MAXLEN][MAXLEN];//輸入所求結點圖的鄰接矩陣intWeight[MAXLEN][MAXLEN];//結點之間的最短路徑矩陣intPath[MAXLEN][MAXLEN][MAXLEN]={0};//存放結點對之間的路徑，初值均為0inti,j,k,n,back=0; n=mg.vexnum; for(i=0;i<n;i++)//cost矩陣初始化 { for(j=0;j<n;j++)Cost[i][j]=mg.arcs[i][j];Cost[i][i]=0; }for(i=0;i<n;i++) {for(j=0;j<n;j++) {Weight[i][j]=Cost[i][j];//將Cost[i][j]復制到Weight[i][j]}}for(k=0;k<n;k++)//對最高下標為k的結點的路徑 {for(i=0;i<n;i++)//對于所有可能的結點對 {for(j=0;j<n;j++) {if(Weight[i][j]>(Weight[i][k]+Weight[k][j])) {Weight[i][j]=Weight[i][k]+Weight[k][j];Path[i][j][k]=k;//將k結點加入到結點對（i，j）的最短路徑中 } }}}printf("有向圖的成本鄰接矩陣\n"); printf("");for(i=0;i<=n;i++)//輸出所求結點圖的鄰接矩陣 {if(i) {printf("v%-6d",i);//打印矩陣的行標v1,v2,……，vn}for(j=0;j<n;j++) {if(!i) {printf("v%-6d",j+1);//打印矩陣的列標 }else{ printf("%-7d",Cost[i-1][j]); }}printf("\n");} printf("\n\n\n");printf("結點對\t\t每對結點之間的最短路徑\t\t\t最短路徑值\n");for(i=0;i<n;i++)//輸出經(jīng)算法產生的結點間的最短路徑矩陣 {for(j=0;j<n;j++) {printf("v%dv%d",i+1,j+1);//打印結點對printf("\t\tv%d->",i+1);//打印每對結點之間的最短路徑for(k=0;k<n;k++) {if(Path[i][j][k])//打印出已存入的路徑 {printf("v%d->",Path[i][j][k]+1); back++; } }printf("v%d",j+1); for(;back>0;back--)//調整輸出格式 printf("\b\b\b\b"); printf("\t\t\t\t\t");printf("%d\n\n",Weight[i][j]);//打印最短路徑值}}}voidoperatemenu()//操作界面{ cout<<endl; cout<<"************************************"<<endl; cout<<"1:Dijkstra"<<endl; cout<<"2:Floyd"<<endl; cout<<"3:重新建圖"<<endl; cout<<"4:退出"<<endl; cout<<"************************************"<<endl;}voidmain(){ MGRAPHmg; cout<<"歡迎使用本系統(tǒng)！"<<endl; mg=create_mgraph();//建立有向圖的鄰接矩陣結構 intchoose,leave=1; while(leave) { operatemenu(); printf("請選擇您需要的操作："); while(1)//判斷選擇是否合法 { if(scanf("%d",&choose)==1&&getchar()=='\n'&&choose>0&&choose<5)break; else { while(getchar()!='\n'); cout<<"請不要隨便亂點！"<<endl; printf("請選擇您需要的操作："); } } printf("\n\n"); switch(choose) { case1:Dijkstra(mg);break; case2:Floyd(mg);break; case3:mg=create_mgraph();break; case4:leave=0;break; default:cout<<"ERROR"<<endl; } } cout<<"歡迎再次使用本操作系統(tǒng)！"<<endl; cout<<"";}設計結果與分析：一：最短路徑問題：如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權值總和達到最小。問題解法邊上權值非負情形的單源最短路徑問題—Dijkstra算法所有頂點之間的最短路徑—Floyd算法1：Dijkstra算法：按路徑長度遞增次序產生最短路徑：把V分成兩組：（1）S：已求出最短路徑的頂點的集合（2）V-S=T：尚未確定最短路徑的頂點集合將T中頂點按最短路徑遞增的次序加入到S中，保證：（1）從源點V0到S中各頂點的最短路徑長度都不大于從V0到T中任何頂點的最短路徑長度（2）每個頂點對應一個距離值S中頂點：從V0到此頂點的最短路徑長度T中頂點：從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度————————具體步驟：初使時令S={V0},T={其余頂點}，T中頂點對應的距離值若存在<V0,Vi>，為<V0,Vi>弧上的權值若不存在<V0,Vi>，為μ從T中選取一個其距離值為最小的頂點W，加入S對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值重復上述步驟，直到S中包含所有頂點，即S=V為止——————————參數(shù)說明：Cost：為兩個節(jié)點間的路徑長，當沒有路徑時為無窮大，當i=j時為0。Dist：為路徑長。Path：為路徑。Flag：指示是否為最短路徑經(jīng)過點。back：調整輸出格式的退格記錄時間復雜度為O(n^2);2：Floyd算法：每對結點之間的最短路徑問題是求滿足下述條件的矩陣A，要求A中的任何元素A（i，j）是代表結點i到結點j的最短路徑的長度?？疾霨中一條由i到j的最路徑，i≠j。這條路徑由i出發(fā)，通過一些中間結點，在j處結束。如果k是這條最短路徑上的一個中間結點，那么由i到k和由k到j的這兩條子路徑應分別是由i到k和由k到j的最短路徑。否則，這條由i到j的路徑就不是具有最小長度的路徑。于是，最優(yōu)性原理成立。如果k是編號最高的中間結點，那么由i到k的這條最短路徑上就不會有比編號k-1更大的結點通過。同樣，在k到j的那條最短路徑上也不會有比編號k-1更大的結點通過。因此，可以把求取一條由i到j的最短路徑看成是如下的過程：首先需要決策哪一個結點是該路徑上具有最大編號的中間結點k，然后就再去求取由i到k和由k到j這兩對結點之間的最短路徑。當然，這兩條路徑上都不可能有比k-1還大的中間結點?！?/p>