課程設(shè)計(jì)報(bào)告---最短路徑求最大利潤

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：22 大?。?09.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩21頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè)計(jì)報(bào)告　　課程名稱：數(shù)據(jù)結(jié)構(gòu) 　　設(shè)計(jì)題目：最短路徑求最大利潤 　　院部：計(jì)算機(jī)與信息工程學(xué)

2、院 　　專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 　　組別： 　　起止日期: 2012年 5月16日 ~2012

3、年 6 月 24日 　　指導(dǎo)教師: 　　目錄　　1 引言1　　2 需求

4、分析1　　2.1 問題描述1　　2.2 功能需求2　　2.3 實(shí)現(xiàn)要點(diǎn)2　　2.4 實(shí)現(xiàn)環(huán)境2　　3 概要設(shè)計(jì)2　　3

5、.1 抽象數(shù)據(jù)類型圖的定義2　　3.2 主程序3　　4 詳細(xì)設(shè)計(jì)3　　4.1 數(shù)學(xué)模型3　　4.2 核心代碼3　　4.2.1定位函數(shù)模塊3&l

6、t;/p>　　4.2.2構(gòu)造無向網(wǎng)G的鄰接矩陣函數(shù)模塊4　　4.2.3鄰接矩陣輸出模塊5　　4.2.4 最短路徑和求最大利潤模塊5　　4.2.5主函數(shù)模塊7　　5 調(diào)試與操作說明：8　　5.1

7、調(diào)試界面8　　5.2 使用說明9　　6 程序設(shè)計(jì)總結(jié)與體會9　　7 致謝11　　8 參考文獻(xiàn)12　　9 附錄13</

8、b>　　1 引言　　“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)學(xué)科的核心課程，而且已成為其他理工科的專業(yè)選修課。　　圖的有關(guān)知識在很多領(lǐng)域有著廣泛的應(yīng)用，在很多情況下是要在尋找兩個頂點(diǎn)之間的最短路徑，本課程設(shè)計(jì)是商品銷售問題，求從滁州銷售商品到各個城

9、市的最大利潤。　　2 需求分析　　2.1問題描述　　現(xiàn)有一批商品，需要從滁州市銷售到另一城市中。圖1給出了滁州市到其余8個城市的距離以及該商品在這8個城市中的銷售價格。圖2給出了這8個城市之間的距離。假設(shè)該商品在滁州市的價格為2元/千克，

10、運(yùn)送1噸商品所需運(yùn)費(fèi)為每公里0.5元，現(xiàn)有10噸商品，編程實(shí)現(xiàn)求從滁州市銷售到各個城市所能獲得的最大利潤。　　表2-1 滁州到各個城市之間的距離及商品在各個城市之間的售價　　表1-2 各個城市之間的距離　　設(shè)計(jì)要求：　?。?）將該圖存

11、儲為鄰接矩陣或鄰接表的形式。　?。?）若這批商品要從滁州市賣往其余各市，需給出選擇走那條路線，并求出所能獲得的最大利潤。　　2.2 功能需求　　要求完成以下功能：　?、?以無向網(wǎng)鄰接矩陣形式輸出表

12、格1和表格2中兩城市間的路徑長度。　?、?輸出從滁州到各城市最短路徑上經(jīng)過的城市及最短路徑長度和商品賣到的最大利潤。　　2.3 實(shí)現(xiàn)要點(diǎn)　?、?輸入城市數(shù)，道路數(shù)和兩城市之間道路長度。　?、?兩城市之間的距離以鄰接矩陣形式存儲。<

13、;/p>　　2.4 實(shí)現(xiàn)環(huán)境　　編成語言：C語言；　　開發(fā)環(huán)境：Window XP ，VC++ 6.0；　　3 概要設(shè)計(jì)　　3.1

14、抽象數(shù)據(jù)類型圖的定義　　ADT Graph{　　數(shù)據(jù)對象V：V是具有相同特性數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。　　數(shù)據(jù)關(guān)系R：　　R={VR}　　VR={（v，

15、w）| v , w∈V, (v , w)表示v和w之間存在路徑}　　基本操作P：　　CreatGraph(&G, V, VR)　　初始條件： V是圖的頂點(diǎn)集，VR是圖中邊的集合。　　操作結(jié)果：按定義(V, VR) 構(gòu)造圖G。

16、　　LocateVex(G, u) 　　初始條件：圖G存在，u和G中頂點(diǎn)具有相同特征。　　操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中“位置” ；否則返回　　其它信息。　　GetVex

17、(G, v) 　　初始條件：圖G存在，v是G中某個頂點(diǎn)。　　操作結(jié)果：返回v的信息。　　InsertVex(&G, v) 　　初始條件：圖G存在，v和G中頂點(diǎn)具有相同特征。　　操作結(jié)果：在圖G中增添新頂點(diǎn)v。<

18、;/p>　　InsertArc(&G, v, w) 　　初始條件：圖G存在，v和w是G中兩個頂點(diǎn)。　　操作結(jié)果：在G中增添弧<v,w>，若G是無向的，則還增添對稱弧<w,v>。　　DeleteArc(&G, v, w)

19、　　初始條件：圖G存在，v和w是G中兩個頂點(diǎn)。　　操作結(jié)果：在G中刪除弧<v,w>，若G是無向的，則還刪除對稱弧<w,v>。　　} ADT Graph　　3.2 主程序　　void mai

20、n( )　　{　　// 輸出圖的鄰接矩陣；　　// 輸入起始點(diǎn)v0；　　// 輸出從滁州到各城市最短路徑上經(jīng)過的城市及最短路徑長度和商品賣到的最大利潤;　　}</b&g

21、t;　　4 詳細(xì)設(shè)計(jì)　　4.1 數(shù)學(xué)模型　　目標(biāo)城市的銷售單價價格減去商品在滁州的價格乘以商品總量再減去運(yùn)費(fèi)，即為滁州到各個城市的所獲的最大利潤。數(shù)學(xué)公式為最大利潤S =(a[v-1]-2)*pow(10,4)-d*0.5*10，a[v-

22、1]為物品在要到達(dá)的城市的單價，d為最短路徑長度；　　4.2 核心代碼　　4.2.1定位函數(shù)模塊　　// 功能：查找頂點(diǎn)在圖中的位置。　　// 輸入：G代表建立的那個無向圖，vert代表在圖中的某個頂點(diǎn)。<

23、;p>　　// 輸出：找到了就輸出該頂點(diǎn)的位置，否則出-1。　　int LocateVex(MGraph G,char *vert)　　{ 　　int i;　　for(i=0; i<

24、;G.vexnum; i++)　　if(strcmp(G.vexs[i],vert)==0)//strcmp 比較兩個字符的大小　　return i;　　return -1;　　}</p&

25、gt;　　4.2.2構(gòu)造無向網(wǎng)G的鄰接矩陣函數(shù)模塊　　// 功能：構(gòu)造無向網(wǎng)鄰接矩陣。　　// 輸入：G代表所要建立的那個圖的參數(shù)。　　// 輸出：建立出這個無向網(wǎng)鄰接矩陣，保存在arcs這個數(shù)組中。　　MGraph CreateGraph_DN(

26、 MGraph G )　　{//建立無向網(wǎng)G的鄰接矩陣　　int i, j, k;　　float w;　　VexType v1[100], v2[100];　　printf("

27、輸入城市數(shù), 城市之間的道路數(shù)：");　　scanf("%d %d", &G.vexnum, &G.arcnum);　　for(i=0; i<G.vexnum; i++) // 讀入所有的頂點(diǎn) 　　{ printf("輸入第%d個城市的信息：&

28、quot;,i+1);　　scanf("%s", &G.vexs[i]);　　}　　for(i=0; i <G.vexnum; i++) //初始化鄰接矩陣 　　for(j=0; j<G.

29、vexnum; j++) 　　G.arcs[i][j].adj=INFINITY;　　for(k=0; k<G.arcnum; k++) { // 輸入所有的邊 　　printf("輸入第%d條道路依附的兩個城市和該道路上的權(quán)值:", k+1);<p

30、>　　scanf("%s %s %f", &v1, &v2, &w);　　// 查詢兩個頂點(diǎn)在圖中存儲的位置，然后對其進(jìn)行相關(guān)賦值　　i = LocateVex(G, v1);　　j = LocateVex(G, v2);<p&

31、gt;　　if (i==-1 || j==-1)　　{printf("輸入的道路不正確\n"); }　　G.arcs[i][j].adj = w;//給相關(guān)兩個頂點(diǎn)邊賦相應(yīng)權(quán)值。　　G.arcs[j][i].adj = w;//因?yàn)檫@是無向圖，所以只要交換里面的頂點(diǎn)位置即可。</p&

32、gt;　　}　　return G;　　}　　4.2.3鄰接矩陣輸出模塊　　// 功能：輸出我們上面那個函數(shù)建立的鄰接矩陣。</p&

33、gt;　　// 輸入：上面建立的那個無向網(wǎng)鄰接矩陣的參數(shù)。　　// 輸出：輸出上面建立的無向網(wǎng)鄰接矩陣，通過界面顯示出來。　　Void print_MGraph(MGraph G)//輸出圖的鄰接矩陣表示　　{&

34、lt;b>　　int i,j;　　/* 鄰接矩陣存儲時用的是一個二維數(shù)組，之前在構(gòu)造鄰接矩陣時，已經(jīng)將相關(guān)邊上的權(quán)值 　　已經(jīng)賦了值. 現(xiàn)在通過兩個for循環(huán)，將這個二維數(shù)組輸出*/　　for(i=0;i<G.vexnum;i++)　　{

35、 for(j=0;j<G.vexnum;j++)　　printf("%f ",G.arcs[i][j].adj ); 　　printf("\n");　　}

36、}　　4.2.4最短路徑和求最大利潤模塊　　// 功能：求最短路徑和最大利潤。　　// 輸入：剛剛建立的這個圖，單源點(diǎn)v0，存儲最短路徑的數(shù)組p，以及存儲最短路徑的權(quán)值大小。　　// 輸出：滁州到各城市的最短路徑距離，最短路徑，滁州到各個城市所能獲得的

37、最大利潤。　　void ShortestPath_DIJ(MGraph G, int v0, int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM], float D[MAX_VERTEX_NUM]){　　float a[]={3.7f,4.0f,3.9f,2.9f,3.3f,3.8f,3.6f,3.6f};//各個城市商品單價存在一

38、個一維數(shù)組中，便于后面調(diào)用，在每個數(shù)字后面加f,是解決當(dāng)時編寫代碼時出現(xiàn)的警告問題，就是為了解決精度問題　　int v, w, i, j, min;　　float S,d;　　int final[MAX_VERTEX_NUM];//標(biāo)志數(shù)組。當(dāng)final[v]為真當(dāng)且僅當(dāng)v屬于S ，即已經(jīng)求的從v0到v的最短路徑

39、　　for(v=0; v<G.vexnum; ++v){　　final[v]=FALSE;//說明還木有從v0到v的最短路徑。　　D[v]=G.arcs[v0][v].adj;//把從v0到v之間邊上的權(quán)值復(fù)制到前面那個數(shù)組　　for(w=0; w<G.vex

40、num; ++w) P[v][w]=FALSE; // 設(shè)空路徑，前面那句話說明w不是v0到v當(dāng)前求得最短路徑上的頂點(diǎn)　　if(D[v]<INFINITY ){　　P[v][v0]=TRUE;　　P[v][v]=TRUE;//說明v0到v之間有權(quán)值，即有路徑。&l

41、t;b>　　}　　}　　D[v0] = 0;　　final[v0] = TRUE; // 初始化，將v0頂點(diǎn)加入S集　　for( i=1; i<G.vexnum; ++i ) {

42、;　　min = INFINITY; // 當(dāng)前所知離v0頂點(diǎn)的最近距離　　for( w=0; w<G.vexnum; ++w )　　if( !final[w] ) // w頂點(diǎn)在V-S中　　if( D[w]<min){<p&

43、gt;　　v = w;　　min=D[w];　　} // w頂點(diǎn)離v0頂點(diǎn)更近　　final[v] = TRUE; // 離v0頂點(diǎn)最近的v加入S集　　for(w

44、=0;w<G.vexnum;++w) { // 更新當(dāng)前最短路徑及距離　　if( !final[w] && (min+G.arcs[v][w].adj<D[w]) ){　　D[w ]= min+G.arcs[v][w].adj;//更新最短路徑上的權(quán)值。　　for( j=0; j&l

45、t;G.vexnum; ++j){　　P[w][j] = P[v][j];　　P[w][w]=TRUE;}//說明j是當(dāng)前v到我這個最短路徑上的頂點(diǎn)　　}　　}<p&

46、gt;　　}　　for( v=1; v<G.vexnum; ++v ){　　if(v!=v0 && D[v]==INFINITY) 　　printf("從城市%s到城市%s無最短路徑\n",G.vexs[v0],G.vexs[v]);

47、　　else if(v!=v0)　　{　　printf("從城市%s到城市%s的最短路徑上經(jīng)過的頂點(diǎn)有",G.vexs[v0],G.vexs[v]);　　printf("(%s",G.vexs[

48、v0]);//在本題中即指滁州，即圖中的單源點(diǎn)　　for( w=1; w<G.vexnum; ++w )　　{　　if(P[v][w]==TRUE && w!=v0 && w!=v) printf(",%s",G.ve

49、xs[w]);//這段代碼就是就是要通過P[][]這個數(shù)組，將v0到v之間的頂點(diǎn)輸出，在本題中就是要輸出從滁州到各個城市之間最短路徑上的城市。　　}　　printf(",%s)",G.vexs[v]);//目的地城市　　d=D[v];//從滁州到各個城市最

50、短路徑上的權(quán)值之和。　　S=(a[v-1]-2)*pow(10,4)-d*0.5*10;//通過這個數(shù)學(xué)函數(shù)求得從滁州到各個城市之間的最大利潤.這里用到之前那個存商品售價的一維數(shù)組。　　printf("最短路徑長度為:%f ",d);　　printf ("從城市%s到城市%s的最大

51、利潤:%f\n",G.vexs[v0],G.vexs[v],S);　　}　　}　　}　　4.2.5主函數(shù)模塊

52、;　　// 功能：調(diào)用相應(yīng)子函數(shù)的功能，實(shí)現(xiàn)相應(yīng)功能。　　void main()　　{　　MGraph G1;　　int v0;　　int P[MAX_V

53、ERTEX_NUM][MAX_VERTEX_NUM];//存儲最短路徑的數(shù)組　　float D[MAX_VERTEX_NUM];//存儲最小權(quán)值的數(shù)組，本題中就是存儲滁州到各個城市最短距離的值。　　G1=CreateGraph_DN( G1 );//調(diào)用構(gòu)造函數(shù)，構(gòu)造一個鄰接矩陣存儲這個實(shí)際問題的數(shù)據(jù)！　　Pri

54、nt_MGraph(G1);//調(diào)用打印函數(shù)，打印出這個鄰接矩陣　　printf("輸入源點(diǎn)v0:");//本題中即指輸入滁州這個城市　　scanf("%d",&v0);　　ShortestPath_DIJ(G1,v0,P,D);//調(diào)用最短路徑函數(shù)求出最短路徑和滁

55、州到各個城市之間所能獲得的最大利潤。　　}　　5 調(diào)試與操作說明：　　5.1 調(diào)試界面　　內(nèi)容如下：⑴.將這個問題抽象化成一個圖的模型，然后構(gòu)造一個無向圖。

56、;　?、?求滁州到各個城市的最短路徑。　　⑶.根據(jù)最短路徑求滁州到各個城市的最大利潤。　　圖5-1 運(yùn)行界面1　　圖5-2 運(yùn)行界面2　　5.2使用說明　　本程序在求最短路徑的問題上采用迪

57、杰斯特拉算法解決，先求出滁州到各個城市之間的最短路徑，再利用數(shù)學(xué)模型解決最大利潤問題。調(diào)試時根據(jù)提示先輸入城市數(shù)和道路數(shù)，再輸入城市信息及城市之間的路徑長度。按Enter鍵，上述信息將以無向網(wǎng)鄰接矩陣形式輸入。再輸入起始點(diǎn)v0(滁州)，即可輸出滁州到各個城市最短路徑上經(jīng)過的城市及路徑長度和最大利潤。　　6 程序設(shè)計(jì)總結(jié)與體會　　課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用

58、所學(xué)知識發(fā)現(xiàn)、提出、分析和解決實(shí)際問題，鍛煉實(shí)踐能力的重要環(huán)節(jié)，是對學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過程。通過這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實(shí)踐相結(jié)合起來，從理論中得出結(jié)論，將結(jié)論用于實(shí)踐，從而提高自己的實(shí)際動手能力和獨(dú)立思考的能力。在設(shè)計(jì)的過程中當(dāng)然遇到了問題，當(dāng)初寫最短路徑的函數(shù)時，改寫書上的算法時，出現(xiàn)了許多問題，還有當(dāng)初我準(zhǔn)備再寫一個子函數(shù)算出到每個城市的最大利

59、潤，但是后來我把各個城市的產(chǎn)品單價通過一個一維數(shù)組存起來，然后通過一個循環(huán)調(diào)用進(jìn)去，很好的解決了這個問題，但是在寫這個數(shù)組時，出現(xiàn)了很多警告，后來在數(shù)組里的各個數(shù)據(jù)里加了f,如后面float a[]={3.7f,4.0f,3.9f,2.9f,3.3f,3.8f,3.6f,3.6f};問題得到解決。還有在輸入時時也遇到了一些問題，就是輸入第幾個城市時，我當(dāng)時想選第一個城市，可是后面的輸出，總是往后面退了一個，這時它會輸出第二個城市到各個城

60、市的最短距離，后來我發(fā)現(xiàn)是我自己理解錯了，代碼沒問題，一維數(shù)組的下標(biāo)從0開始。由于本程序要輸入　　7 致謝 　　在寫本程序時，調(diào)試出現(xiàn)警告，在網(wǎng)上發(fā)帖（csdn論壇），后解決，感謝網(wǎng)友的幫助。　　同時在撰寫課程設(shè)計(jì)報(bào)告時，感謝趙瑞斌老師和楊傳建老師的幫助，幫助我們改寫文檔格式

61、，簡化內(nèi)容，排版，幫助我們調(diào)試代碼。　　8 參考文獻(xiàn)　　[1] 嚴(yán)蔚敏,吳偉民編著.數(shù)據(jù)結(jié)構(gòu)（c語言版）[M].北京:清華大學(xué)出版社，2011.　　[2] 趙波主編.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（c語言版）[M]. 清華大學(xué)出版社，2010.&l

62、t;b>　　9 附錄　　#include <stdio.h>　　#include <stdlib.h>　　#include <math.h>　　#include "malloc.h"<

63、/p>　　#include "string.h"　　#define INFINITY 10000// 用整型最大值代替∞　　#define MAX_VERTEX_NUM 20 // 最大頂點(diǎn)個數(shù)　　#define OK 1

64、　　#define ERROR 0　　#define FALSE 0　　#define TRUE 1　　#define MAXQSIZE100 　　typedef int QElemType;　　typedef float VRT

65、ype;　　typedef float InfoType;　　typedef char VertexType;　　typedef char VexType;　　//============鄰接矩陣的定義============

66、　　typedef struct {　　VRType adj; 　　InfoType info; // 該弧相關(guān)信息的指針(可無) 　　}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];　　typedef str

67、uct {　　VertexType vexs[MAX_VERTEX_NUM][100]; // 頂點(diǎn)向量　　AdjMatrix arcs; // 鄰接矩陣　　int vexnum,arcnum; // 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)　　} MGraph ;&

68、lt;p>　　//=======================鄰接矩陣的定義========　　int LocateVex(MGraph G,char *vert)　　{ int i;　　for(i=0; i<G.vexnum; i++)　　if(str

69、cmp(G.vexs[i],vert)==0)　　return i;　　return -1;　　}　　MGraph CreateGraph_DN( MGraph G ){//建立無向網(wǎng)G的鄰接矩

70、陣　　int i, j,k;　　float w;　　VexType v1[100], v2[100];　　printf("輸入城市數(shù),城市之間的道路數(shù)：");　　sca

71、nf("%d %d", &G.vexnum, &G.arcnum);　　for(i=0; i<G.vexnum; i++) // 讀入所有的頂點(diǎn) 　　{ printf("輸入第%d個城市的信息：",i+1);　　scanf("%s&q

72、uot;, &G.vexs[i]);　　}　　for(i=0; i <G.vexnum; i++) //初始化鄰接矩陣 　　for(j=0; j<G.vexnum; j++) 　　G.arcs[i][j].

73、adj=INFINITY;　　for(k=0; k<G.arcnum; k++) { // 輸入所有的邊 　　printf("輸入第%d條道路依附的兩個城市和該道路上的權(quán)值:",k+1);　　scanf("%s %s %f", &v1, &v2,

74、 &w);　　// 查詢兩個頂點(diǎn)在圖中存儲的位置 　　i = LocateVex(G, v1);　　j = LocateVex(G, v2);　　if (i==-1 || j==-1)　　{printf("輸

75、入的道路不正確\n"); }　　G.arcs[i][j].adj = w;　　G.arcs[j][i].adj = w;　　}　　return G;<p&g

76、t;　　}　　void Print_MGraph(MGraph G)//輸出圖的鄰接矩陣表示　　{　　int i,j;　　for(i=0;i<G.vex

77、num;i++)　　{ for(j=0;j<G.vexnum;j++)　　printf("%f ",G.arcs[i][j].adj ); /*鄰接矩陣*/　　printf("\n");　　} &l

78、t;/b>　　}　　void ShortestPath_DIJ(MGraph G, int v0, int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM], float D[MAX_VERTEX_NUM]){　　float a[]={3.7f,4.0

79、f,3.9f,2.9f,3.3f,3.8f,3.6f,3.6f};　　int v, w, i, j, min;　　float S,d;　　int final[MAX_VERTEX_NUM];　　for(v=0; v<G.vexnum; ++v){

80、　　final[v]=FALSE;　　D[v]=G.arcs[v0][v].adj;　　for(w=0; w<G.vexnum; ++w) P[v][w]=FALSE; // 設(shè)空路徑　　if(D[v]<INFINITY ){　　P[v

81、][v0]=TRUE;　　P[v][v]=TRUE;　　}　　}　　D[v0] = 0;　　final[v0] = TRUE; // 將v0頂點(diǎn)加入

82、S集　　for( i=1; i<G.vexnum; ++i ) {　　min = INFINITY; // 當(dāng)前所知離v0頂點(diǎn)的最近距離　　for( w=0; w<G.vexnum; ++w )　　if( !final[w] ) //

83、w頂點(diǎn)在V-S中　　if( D[w]<min){　　v = w;　　min=D[w];　　} // w頂點(diǎn)離v0頂點(diǎn)更近　　fi

84、nal[v] = TRUE; // 離v0頂點(diǎn)最近的v加入S集　　for(w=0;w<G.vexnum;++w) { // 更新當(dāng)前最短路徑及距離　　if( !final[w] && (min+G.arcs[v][w].adj<D[w]) ){　　D[w ]= min+

85、G.arcs[v][w].adj;　　for( j=0; j<G.vexnum; ++j){　　P[w][j] = P[v][j];　　P[w][w]=TRUE;}　　}

86、;　　}　　}　　for( v=1; v<G.vexnum; ++v ){　　if(v!=v0 && D[v]==INFINITY) 　　printf("從城市%s到城市%s無最短路

87、徑\n",G.vexs[v0],G.vexs[v]);　　else if(v!=v0)　　{　　printf("從城市%s到城市%s的最短路徑上經(jīng)過的頂點(diǎn)有",G.vexs[v0],G.vexs[v]);

88、　　printf("(%s",G.vexs[v0]);　　for( w=1; w<G.vexnum; ++w )　　{　　if(P[v][w]==TRUE && w!=v0 && w!=v) printf("

89、,%s",G.vexs[w]);　　}　　printf(",%s)",G.vexs[v]);　　d=D[v];　　S=(a[v-1]-2)*pow(10,4)-d*0

90、.5*10;　　printf("最短路徑長度為:%f ",d);　　printf ("從城市%s到城市%s的最大利潤:%f\n",G.vexs[v0],G.vexs[v],S);　　}<

91、b>　　}　　}　　//===========================最短路徑===================　　void main()　　{</p&

92、gt;　　MGraph G1;　　int v0;　　int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM];　　float D[MAX_VERTEX_NUM];　　G1=CreateGraph

93、_DN( G1 );　　Print_MGraph(G1);　　printf("輸入源點(diǎn)v0:");　　scanf("%d",&v0);　　ShortestPath_DIJ(G1,v0,P,D);&l

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設(shè)計(jì)報(bào)告---最短路徑求最大利潤

文檔簡介

溫馨提示

最新文檔

評論

課程設(shè)計(jì)報(bào)告---最短路徑求最大利潤

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載