軟件課程設(shè)計(jì)報(bào)告 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑

任務(wù)書(shū)PAGE1北京信息科技大學(xué)計(jì)算機(jī)軟件基礎(chǔ)課程設(shè)計(jì)題目：從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑學(xué)院：光電信息與通信工程學(xué)院專業(yè)：通信工程專業(yè)學(xué)生姓名：班級(jí)/學(xué)號(hào)指導(dǎo)老師：起止時(shí)間：題目7從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑（難度系數(shù)10，全部做出給100分）主要內(nèi)容假設(shè)西安、北京、沈陽(yáng)、武漢4個(gè)城市構(gòu)成小型交通網(wǎng)，4個(gè)城市表示圖的4個(gè)頂點(diǎn)，他們構(gòu)成了無(wú)向連通圖。以北京為源點(diǎn)，求北京到西安的最短路徑；求北京到沈陽(yáng)的最短路徑；求北京到武漢的最短路徑。學(xué)會(huì)建立圖的鄰接表，理解圖的基本概念。學(xué)會(huì)編寫(xiě)DLL函數(shù)。根據(jù)自己構(gòu)建的連通圖，利用Dijkstra算法求從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑。掌握C++編程環(huán)境的基本調(diào)試方法，熟練使用可視化C++編程工具。設(shè)計(jì)要求1、上交課程設(shè)計(jì)的書(shū)面材料，要求打印。包括課程設(shè)計(jì)任務(wù)書(shū)、主要內(nèi)容，源程序，對(duì)程序的功能進(jìn)行客觀評(píng)價(jià)，明確指出自己編寫(xiě)了哪些具體函數(shù)。2、上交電子版源程序，包括鄰接表建立程序、Dijkstra算法。3、自己編寫(xiě)一個(gè)求素?cái)?shù)函數(shù)，把它書(shū)寫(xiě)成一個(gè)動(dòng)態(tài)鏈接庫(kù)形式，并在主函數(shù)中調(diào)用它。嘗試把自己編寫(xiě)的程序?qū)懗蓜?dòng)態(tài)鏈接庫(kù)和靜態(tài)鏈接庫(kù)形式（無(wú)需上交），并比較以下三種EXE文件的大小。A：調(diào)用靜態(tài)鏈接庫(kù)生成的EXE執(zhí)行文件。B：調(diào)用動(dòng)態(tài)鏈接庫(kù)生成的EXE執(zhí)行文件。C：直接調(diào)用函數(shù)生成的EXE執(zhí)行文件。主要儀器設(shè)備計(jì)算機(jī)一臺(tái)，安裝WindowsXP操作系統(tǒng)、MicrosoftVisualC++6.0、MSDNLibrary。主要參考文獻(xiàn)[1]侯俊杰.深入淺出MFC(第二版)[M].武漢：華中科技大學(xué)出版社,2001.[2]譚浩強(qiáng).C程序設(shè)計(jì)（第二版）[M].北京：清華大學(xué)出版社,1999..[3]孟彩霞.計(jì)算機(jī)軟件基礎(chǔ)[M].陜西：西安電子科技大學(xué)出版社,2003.[4]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社,2005.課程設(shè)計(jì)進(jìn)度計(jì)劃（起止時(shí)間、工作內(nèi)容）選做最短路徑題目的同學(xué)，2人1組，1人做Dijkstra算法，1人做Floyd算法，整個(gè)課程設(shè)計(jì)共20學(xué)時(shí)，具體進(jìn)度如下：4學(xué)時(shí)了解課題背景，選題，學(xué)習(xí)DLL，學(xué)習(xí)圖的基本概念。4學(xué)時(shí)編寫(xiě)鄰接表建立程序。4學(xué)時(shí)Floyd算法。4學(xué)時(shí)嘗試?yán)肍loyd算法求任意兩個(gè)頂點(diǎn)之間的最小距離。4學(xué)時(shí)調(diào)試程序，答辯。課程設(shè)計(jì)開(kāi)始日期第3周周二課程設(shè)計(jì)完成日期第7周周二課程設(shè)計(jì)實(shí)驗(yàn)室名稱計(jì)算中心機(jī)房地點(diǎn)健翔橋校區(qū)摘要PAGE17摘要本次課程設(shè)計(jì)的問(wèn)題：假設(shè)西安、北京、沈陽(yáng)、武漢4個(gè)城市構(gòu)成小型交通網(wǎng)，4個(gè)城市表示圖的4個(gè)頂點(diǎn)，它們構(gòu)成了無(wú)向連通圖。以北京為源點(diǎn)，求北京到西安的最短路徑；求北京到沈陽(yáng)的最短路徑；北京到武漢的最短路徑。本次課程設(shè)計(jì)中應(yīng)用Floyd算法求最短路徑。通過(guò)一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑矩陣，從圖的帶權(quán)鄰接矩陣A=[a(i,j)]n×n開(kāi)始，遞歸地進(jìn)行n次更新，按一個(gè)公式，構(gòu)造出矩陣D(1)，又用同樣地公式由D(1)構(gòu)造出D(2)…最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑長(zhǎng)度，稱D(n)為圖的距離矩陣，同時(shí)還可引入一個(gè)后繼節(jié)點(diǎn)矩陣path來(lái)記錄兩點(diǎn)間的最短路徑。本次試驗(yàn)可以進(jìn)行有向和無(wú)向的計(jì)算，不同城市之間的距離由開(kāi)始進(jìn)行輸入，最后顯示兩個(gè)城市之間的最短路徑。正文—從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑一、應(yīng)用弗洛伊德（Floyd）算法計(jì)算最短路徑假設(shè)西安、北京、沈陽(yáng)、武漢4個(gè)城市構(gòu)成小型交通網(wǎng)，4個(gè)城市表示圖的4個(gè)頂點(diǎn)，他們構(gòu)成了無(wú)向連通圖。以北京為源點(diǎn)，求北京到西安的最短路徑；求北京到沈陽(yáng)的最短路徑；求北京到武漢的最短路徑。二、弗洛伊德（Floyd）算法的基本思想Floyd算法是通過(guò)權(quán)矩陣計(jì)算來(lái)實(shí)現(xiàn)的一種方法，其主要思想是從代表任意兩個(gè)節(jié)點(diǎn)vi到vj的距離的帶權(quán)鄰接矩陣D(0)開(kāi)始，首先計(jì)算D(1)，即計(jì)算vi到vj的距離。經(jīng)過(guò)一次經(jīng)轉(zhuǎn)的所有可能路徑，經(jīng)過(guò)比較后選出最短路，代替D(0)中對(duì)應(yīng)的路徑，迭代列出距離矩陣D(1)，D(1)中各元素表示通過(guò)一次迭代后網(wǎng)絡(luò)中任意兩點(diǎn)間最短路，也即網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)或只經(jīng)過(guò)一個(gè)中間點(diǎn)時(shí)的最短路。在此基礎(chǔ)上依次計(jì)算D(2),D(3),…,D(k)，D(k)中對(duì)應(yīng)的元素表示任意兩點(diǎn)間不經(jīng)過(guò)中間點(diǎn)或最多允許經(jīng)過(guò)2k-1個(gè)中間點(diǎn)時(shí)的最短路。當(dāng)D(k+1)=D(k)時(shí)，表明得到的帶權(quán)鄰接矩陣D(k)就反映了所有頂點(diǎn)對(duì)之間的最短距離信息,，成為最短距離矩陣。三、floyd算法函數(shù)四、基本流程Floyd采用動(dòng)態(tài)規(guī)劃余力和逐步優(yōu)化激素和，對(duì)有向帶權(quán)圖G=（V,E）設(shè)計(jì)出求每對(duì)定點(diǎn)見(jiàn)最短路徑的方法。該剛發(fā)使用鄰接矩陣表示有向帶權(quán)圖G，有向圖中的n個(gè)頂點(diǎn)從1開(kāi)始編號(hào)。初始時(shí)，用鄰接矩陣adges存儲(chǔ)有向圖G，即頂點(diǎn)i到j(luò)的最短路徑長(zhǎng)度adges[i][j]就是弧所對(duì)應(yīng)的權(quán)值，它表示任意頂點(diǎn)對(duì)之間不經(jīng)過(guò)任何中間頂點(diǎn)的最短路徑和長(zhǎng)度。要求頂點(diǎn)i到j(luò)記得最短路徑長(zhǎng)度，對(duì)每一對(duì)頂點(diǎn)的路徑進(jìn)行比較存儲(chǔ)的試探，累加遞歸后產(chǎn)生一個(gè)n階路徑矩陣序列A，算法結(jié)束時(shí)，從該矩陣可以查找到i到j(luò)的最短路徑上的所有點(diǎn)。voidpathchange(inti,intj,intk)//路徑處理函數(shù){intm,n,p,q;for(m=0;m<max;m++){path[i][j].distance[m]=-1;}//首先將其初始化計(jì)算兩點(diǎn)之間的距離for(q=0;q<max;q++){ if(path[i][k].distance[q]!=-1) {m++; } else { break; }}//獲取path[i][k]的長(zhǎng)度為mfor(q=0;q<max;q++){ if(path[k][j].distance[q]!=-1) {n++; } else { break; }}//獲取path[k][j]的長(zhǎng)度為n五、功能實(shí)現(xiàn)1、設(shè)定ABCD四個(gè)城市，之間全連通，無(wú)向。結(jié)果如下：輸入：結(jié)果：2、設(shè)定ABCD四個(gè)城市、之間為非全連通，無(wú)向。輸入：結(jié)果：3、設(shè)定ABCD四個(gè)城市、全連通，有向輸入：結(jié)果：4、設(shè)定ABCD四個(gè)城市、非全連通、有向。輸入：結(jié)果：5、ABCD四個(gè)城市，A、C之間的最短距離是ABC截圖如下：代碼：extern"C"_declspec(dllexport)intsushu(intn){inti;for(i=2;i<n;i++) if(n%i) return1; elsereturn0;}#include"stdafx.h"extern"C"_declspec(dllimport)intsushu(inti);intmain(intargc,char*argv[]){inti=1,m;printf("輸入的數(shù)字為:");scanf("%d",&m);printf("素?cái)?shù)有：\n");while(i+1<=m){i++;if(sushu(i))printf("%d\t",i);}return0;}截圖如下：七、心得體會(huì)參考文獻(xiàn)參考文獻(xiàn)源代碼源代碼：#include"stdio.h"#definemax100structplace{charname[max];}pla[max];//地域名稱structpath{intdistance[max];}path[max][max];//行進(jìn)路線inta[max][max]={0};voidpathchange(inti,intj,intk)//路徑處理函數(shù){intm,n,p,q;for(m=0;m<max;m++){path[i][j].distance[m]=-1;}//首先將其初始化m=0;n=0;for(q=0;q<max;q++){ if(path[i][k].distance[q]!=-1) {m++; } else { break; }}//獲取path[i][k]的長(zhǎng)度為mfor(q=0;q<max;q++){ if(path[k][j].distance[q]!=-1) {n++; } else { break; }}//獲取path[k][j]的長(zhǎng)度為nfor(p=0;p<m;p++){path[i][j].distance[p]=path[i][k].distance[p];//將path[i][k]的內(nèi)容轉(zhuǎn)到path[i][j]中去}for(p=0;p<n;p++){path[i][j].distance[p+m]=path[k][j].distance[p];//將path[k][j]的內(nèi)容轉(zhuǎn)到path[i][j]中去}}voidcin(int*p)//賦值和路線函數(shù)初始化函數(shù){printf("請(qǐng)輸入城市的個(gè)數(shù)(大于二)\n");scanf("%d",p);while(*p<=2){printf("輸入值不合法請(qǐng)重新輸入\n");scanf("%d",p); }inti=0,j=0,k=0;for(i=0;i<max;i++)//為了多次循環(huán)而進(jìn)行的初始化{ for(j=0;j<max;j++) { a[i][j]=0; }} for(i=0;i<*p;i++) { for(j=0;j<*p;j++) for(k=0;k<max;k++) { if(k==0) { path[i][j].distance[k]=i; } else { if(k==1) { path[i][j].distance[k]=j; } elsepath[i][j].distance[k]=-1; } } }}voidbegin(intn,intchoo)//初始化函數(shù)2{inti=0,j=0;for(i=1;i<=n;i++){printf("請(qǐng)輸入第");printf("%d",i);printf("個(gè)城市的名字\n");scanf("%s",pla[i-1].name);} for(i=0;i<n;i++){ for(j=0;j<n;j++) {if(i==j) { a[i][j]=0; } else{ switch(choo) { case1:printf("請(qǐng)輸入");printf("%s",pla[i].name);printf("到"); printf("%s",pla[j].name);printf("的距離(不通請(qǐng)輸入-1)\n"); scanf("%d",&a[i][j]);break; case2: if(j>i) { printf("請(qǐng)輸入");printf("%s",pla[i].name);printf("到"); printf("%s",pla[j].name);printf("的距離(不通請(qǐng)輸入-1)\n");scanf("%d",&a[i][j]); }break; } } }}if(choo==2){for(i=0;i<n;i++){ for(j=0;j<n;j++) { a[j][i]=a[i][j]; } }}}voidfloyd(intn)//floyd算法函數(shù){inti=0,j=0,k=0;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]) { if(a[i][k]!=-1&&a[k][j]!=-1) { a[i][j]=a[i][k]+a[k][j];pathchange(i,j,k); } } } } }}intchoose(){intnum,num_check; printf("請(qǐng)選擇兩城市間是有向圖還是無(wú)向圖\n"); printf("1有向(城市間來(lái)回距離可以不一樣)\n"); printf("2無(wú)向(城