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

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