2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩21頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、<p><b>  課程設計報告</b></p><p>  課程名稱: 數(shù)據(jù)結構 </p><p>  設計題目: 最短路徑求最大利潤 </p><p>  院 部: 計算機與信息工程學

2、院 </p><p>  專 業(yè): 計算機科學與技術 </p><p>  組 別: </p><p>  起止日期: 2012年 5月16日 ~2012

3、年 6 月 24日 </p><p>  指導教師: </p><p><b>  目 錄</b></p><p><b>  1 引言1</b></p><p><b>  2 需求

4、分析1</b></p><p>  2.1 問題描述1</p><p>  2.2 功能需求2</p><p>  2.3 實現(xiàn)要點2</p><p>  2.4 實現(xiàn)環(huán)境2</p><p><b>  3 概要設計2</b></p><p>  3

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

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

7、 調試界面8</p><p>  5.2 使用說明9</p><p>  6 程序設計總結與體會9</p><p><b>  7 致謝11</b></p><p><b>  8 參考文獻12</b></p><p><b>  9 附錄13</

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

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

10、運送1噸商品所需運費為每公里0.5元,現(xiàn)有10噸商品,編程實現(xiàn)求從滁州市銷售到各個城市所能獲得的最大利潤。</p><p>  表2-1 滁州到各個城市之間的距離及商品在各個城市之間的售價</p><p>  表1-2 各個城市之間的距離</p><p><b>  設計要求:</b></p><p>  (1)將該圖存

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

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

13、;/p><p><b>  2.4 實現(xiàn)環(huán)境</b></p><p><b>  編成語言:C語言;</b></p><p>  開發(fā)環(huán)境:Window XP ,VC++ 6.0;</p><p><b>  3 概要設計</b></p><p>  3.1

14、抽象數(shù)據(jù)類型圖的定義</p><p>  ADT Graph{</p><p>  數(shù)據(jù)對象V:V是具有相同特性數(shù)據(jù)元素的集合,稱為頂點集。</p><p><b>  數(shù)據(jù)關系R:</b></p><p><b>  R={VR}</b></p><p>  VR={(v,

15、w)| v , w∈V, (v , w)表示v和w之間存在路徑}</p><p><b>  基本操作P:</b></p><p>  CreatGraph(&G, V, VR)</p><p>  初始條件: V是圖的頂點集,VR是圖中邊的集合。</p><p>  操作結果: 按定義(V, VR) 構造圖G。

16、</p><p>  LocateVex(G, u) </p><p>  初始條件: 圖G存在,u和G中頂點具有相同特征。</p><p>  操作結果: 若G中存在頂點u,則返回該頂點在圖中“位置” ;否則返回</p><p><b>  其它信息。</b></p><p>  GetVex

17、(G, v) </p><p>  初始條件: 圖G存在,v是G中某個頂點。</p><p>  操作結果: 返回v的信息。</p><p>  InsertVex(&G, v) </p><p>  初始條件: 圖G存在,v和G中頂點具有相同特征。</p><p>  操作結果: 在圖G中增添新頂點v。<

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

19、<p>  初始條件: 圖G存在,v和w是G中兩個頂點。</p><p>  操作結果: 在G中刪除弧<v,w>,若G是無向的,則還刪除對稱弧<w,v>。</p><p>  } ADT Graph</p><p><b>  3.2 主程序</b></p><p>  void mai

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

21、t;</p><p><b>  4 詳細設計</b></p><p><b>  4.1 數(shù)學模型</b></p><p>  目標城市的銷售單價價格減去商品在滁州的價格乘以商品總量再減去運費,即為滁州到各個城市的所獲的最大利潤。數(shù)學公式為最大利潤S =(a[v-1]-2)*pow(10,4)-d*0.5*10,a[v-

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

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

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

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

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

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

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

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

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

31、gt;  if (i==-1 || j==-1)</p><p>  {printf("輸入的道路不正確\n"); }</p><p>  G.arcs[i][j].adj = w;//給相關兩個頂點邊賦相應權值。</p><p>  G.arcs[j][i].adj = w;//因為這是無向圖,所以只要交換里面的頂點位置即可。</p&

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

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

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

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

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

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

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

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

40、num; ++w) P[v][w]=FALSE; // 設空路徑,前面那句話說明w不是v0到v當前求得最短路徑上的頂點</p><p>  if(D[v]<INFINITY ){</p><p>  P[v][v0]=TRUE;</p><p>  P[v][v]=TRUE;//說明v0到v之間有權值,即有路徑。</p><p>&l

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

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

43、gt;<b>  v = w;</b></p><p><b>  min=D[w];</b></p><p>  } // w頂點離v0頂點更近</p><p>  final[v] = TRUE; // 離v0頂點最近的v加入S集</p><p>  for(w

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

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

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

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

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

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

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

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

52、;  // 功能:調用相應子函數(shù)的功能,實現(xiàn)相應功能。</p><p>  void main()</p><p><b>  {</b></p><p>  MGraph G1;</p><p><b>  int v0;</b></p><p>  int P[MAX_V

53、ERTEX_NUM][MAX_VERTEX_NUM];//存儲最短路徑的數(shù)組</p><p>  float D[MAX_VERTEX_NUM];//存儲最小權值的數(shù)組,本題中就是存儲滁州到各個城市最短距離的值。</p><p>  G1=CreateGraph_DN( G1 );//調用構造函數(shù),構造一個鄰接矩陣存儲這個實際問題的數(shù)據(jù)!</p><p>  Pri

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

55、州到各個城市之間所能獲得的最大利潤。</p><p><b>  }</b></p><p>  5 調試與操作說明:</p><p><b>  5.1 調試界面</b></p><p>  內容如下:⑴.將這個問題抽象化成一個圖的模型,然后構造一個無向圖。</p><p>

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

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

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

59、潤,但是后來我把各個城市的產(chǎn)品單價通過一個一維數(shù)組存起來,然后通過一個循環(huá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};問題得到解決。還有在輸入時時也遇到了一些問題,就是輸入第幾個城市時,我當時想選第一個城市,可是后面的輸出,總是往后面退了一個,這時它會輸出第二個城市到各個城

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

61、,簡化內容,排版,幫助我們調試代碼。</p><p><b>  8 參考文獻</b></p><p>  [1] 嚴蔚敏,吳偉民編著.數(shù)據(jù)結構(c語言版)[M].北京:清華大學出版社,2011.</p><p>  [2] 趙波主編.數(shù)據(jù)結構實用教程(c語言版)[M]. 清華大學出版社,2010.</p><p>&l

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

81、][v0]=TRUE;</p><p>  P[v][v]=TRUE;</p><p><b>  }</b></p><p><b>  }</b></p><p>  D[v0] = 0;</p><p>  final[v0] = TRUE; // 將v0頂點加入

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

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

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

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

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

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

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

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

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

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

92、gt;<p>  MGraph G1;</p><p><b>  int v0;</b></p><p>  int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM];</p><p>  float D[MAX_VERTEX_NUM];</p><p>  G1=CreateGraph

93、_DN( G1 );</p><p>  Print_MGraph(G1);</p><p>  printf("輸入源點v0:");</p><p>  scanf("%d",&v0);</p><p>  ShortestPath_DIJ(G1,v0,P,D);</p>&l

溫馨提示

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

評論

0/150

提交評論