數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖頂點間最短路徑算法

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖頂點間最短路徑算法_第1頁

已閱讀1頁，還剩13頁未讀，繼續(xù)免費閱讀

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計　　設(shè)計題目：圖頂點間最短路徑算法　　專業(yè)：計算機科學與技術(shù)　　班級： 　　姓名： </p

2、>　　學號： 　　指導老師： 　　完成時間：2009-5-9　　一：需求分析：　　問題描述：路徑問題在圖論中

3、占有重要位置，因為這與日常生活中的許多問題有著廣泛的聯(lián)系。比如乘汽車旅行時，我們總希望找出到目的地盡可能短的線路；如果在地圖上標出每兩個路口之間的距離，如何找出一條最短的行車路線？在這個例子中我們可以把地圖模型化為一個圖，結(jié)點表示一段公路的起點和終點，邊的權(quán)值表示公路的長度。我們的目標是從起點出發(fā)找出一條到達目的地的最短路徑。一種直接的方法就是列舉出所有的路徑，并計算出每條路徑的長度，然后選擇最短的一條。容易看出，即使不考慮包含回路的路

4、徑，在起點和終點之間依然可能存在很多不同的行車路線，而其中絕大多數(shù)是不必考慮的。　　二：概要設(shè)計　　設(shè)計思想：　?、?Dijkstra算法的基本思想：　　這種算法是解決有向圖的最短路徑問題的條件是

5、該圖所有邊的權(quán)值是非負值。Dijkstra 算法定義了一結(jié)點集合，從源結(jié)點到集合是任一點的最短路徑的權(quán)值均已確定。算法反復地從集合中挑選出其最短路徑估計為最小的結(jié)點，并將最小結(jié)點插入集合，并對和最小結(jié)點相鄰的所有邊進行松弛。　?、?Bellman-ford算法的基本思想：　　Floyd能在邊的權(quán)值為負的情況下解決單源最短路徑問題。已知有向加權(quán)圖G=（V，

6、E），設(shè)其源結(jié)點為S，加權(quán)函數(shù)w：E→R，對該圖運行FLOYD算法可返回一布爾值，表有圖中是否存在一個從源結(jié)點可達的權(quán)值為負的回路。如果存在這樣的回路，則算法返回FLASE，說明該問題無解。若不存在這樣的回路，算法將產(chǎn)生最短路徑及其權(quán)值Floyd算法運用了松弛技術(shù)，對每一個結(jié)點并逐步減小從源到的最短路徑的權(quán)值的估計值直至達到實際的最短路徑.　?、?Floyd算法基本思想：

7、　　設(shè)帶權(quán)圖G=(V,E)，有N個頂點，圖采用鄰接矩陣作為存儲結(jié)構(gòu)。Floyd算法是以關(guān)系矩陣為基礎(chǔ)，把關(guān)系矩陣看成是沒有經(jīng)過任何中間結(jié)點，直接可以到達的每一對頂點間的最短路徑的完整表示，然后經(jīng)過多次迭代，每次增加一個新結(jié)點，在允許這個結(jié)點作為中間結(jié)點的條件下，計算每一對頂點間的最短路徑的縮短變化，直到所有結(jié)點都可以考慮進去為止，結(jié)果得到第一對頂點間的最短路徑。主要計算過程是在關(guān)系矩陣上的迭代和修改。</p&g

8、t;　　返回布爾值TRUE當且僅當圖中不包含從源結(jié)點可達的負權(quán)值回路。　　三詳細設(shè)計：　　一般地，在最短路徑問題中，給出一有向圖G=(V,E)，以及在其上定義的加權(quán)函數(shù)w:E→R 路徑p()的權(quán)是指構(gòu)成路徑的所有邊的權(quán)值之和，即　　從U到V之間的最短路徑

9、的權(quán)值為　　從結(jié)點到的最短路徑的權(quán)值。　?。罕硎镜淖疃搪窂綐渲械牡母附Y(jié)點　?。罕硎緩脑唇Y(jié)點到的最短路徑權(quán)值的上界　　G=（V，E）是有向加權(quán)圖，其中加權(quán)函數(shù)為 S為源結(jié)點　　通過下面的算法對進行初始化：&l

10、t;p>　　INITIALIZE-SINGLE-SOURCE(G,s)　　{ for (每一個結(jié)點)　　{；　??；}　??；

11、　　}　　經(jīng)初始化以后，對所有的，有；對-{s}，有且。采用松弛技術(shù)去松弛一條邊的過程包括測試是否可能通過結(jié)點對迄今找出從S到V的最短路徑進行改進。如果可能，則更新和。一次松弛操作可以減小最短路徑估計值并更新的祖先域，下面過程實現(xiàn)對邊進行一次松弛操作。　　RELAX</b

12、>　　{if (>+)　　{=+;　　=u;　　}<b&

13、gt;　　}　　Dijkstra 算法描述：　　輸入：G=(V,E),加權(quán)函數(shù)w,源結(jié)點s　　輸出：從源s到v的最短路徑　　Algorithm DIJKSTRA (G,W,S)　　{ Initialize-si

14、ngle-source(G,s)　　S=；　　Q=V[G]；while(Q!= )do 　　{u=extraqct-min(Q);　　S=S;　　fo

15、r(每一個結(jié)點vAdj[u])　　RELAX;　　}　　}　　Bellman-Ford 算法描述：　　輸入：G=(V

16、,E),加權(quán)函數(shù)w,源結(jié)點s　　輸出：從源s到v的最短路徑　　Algorithm BELLMAN-FORD (G,W,S)　　{Initialize-single-source(G,s);　　For(i=1 to |V[G]|-1)

17、;　　for(每一條邊（u,v）E[G])　　RELAX;　　for(每一條邊（u,v）E[G])　　if(>+)　　return false;

18、return true;　　}　　Floyd算法描述：　　void Floyd(){　　int i,j,k;　　for(k=1;k<=n;k++)

19、;　　for(i=1;i<=n;i++)　　for(j=1;j<=n;j++)　　if(dist[i][k]+dist[k][j]<dist[i][j])　　dist[i][j]=dist[i][k]+dist[k][j];　　Dijkstra算法流程&

20、lt;/p>　　在以下說明中，s為源，w[u,v]為點u和v之間的邊的長度，結(jié)果保存在dist[] 　　（1）初始化：源的距離dist[s]設(shè)為0，其他的點距離設(shè)為無窮大，同時把所有的點的狀態(tài)設(shè)沒有擴展過。 　?。?）循環(huán)n-1次： 　　在沒有擴展過的點中取一距離最小的點u，并將其狀態(tài)

21、設(shè)為已擴展。對于每個與u相鄰的點v，執(zhí)行Relax(u,v)，也就是說，如果dist[u]+w[u,v]<dist[v]，那么把dist[v]更新成更短的距離dist[u]+w[u,v]。此時到點v的最短路徑上，前一個節(jié)點即為u結(jié)束。此時對于任意的u，dist[u]就是s到u的距離.　　Bellman-Ford算法流程分為三個階段：　?。?）初始化

22、：將除源點外的所有頂點的最短距離估計值 d[v] ←+∞, d[s] ←0;　　（2）迭代求解：反復對邊集E中的每條邊進行松弛操作，使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離；（運行|v|-1次）　?。?）檢驗負權(quán)回路：判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法返回false，表明問題無解；否則算法返回tru

23、e，并且從源點可達的頂點v的最短距離保存在 d[v]中。　　Floyd 算法流程：（1）首先Ｓ以邊集Ｍ初始化，得到所有的直接連通代價；（2）依次考慮第k個結(jié)點，對于Ｓ中的每一個Ｓ[i][j]，判斷是否滿足：　　S[i][j]>S[i][k]+S[k][j]，如果滿足則用S[i][k]+S[k][j]代替Ｓ[i][j]，此為第k步；（3）k循環(huán)取遍所有結(jié)點，算法結(jié)束時，Ｓ為最終解。&l

24、t;/p>　　Dijkstra算法的數(shù)據(jù)結(jié)構(gòu)：　　typedef struct{　　AdjType length;/*最短路徑長度 */　　int prevex;/*從到（i=1,2,……n）的最短路徑上的前趨頂點 */<

25、;b>　　}Path;　　path.dist;　　Floyd 算法的數(shù)據(jù)結(jié)構(gòu)：　　Typedef struct{　　AdjType *a[];/*存放每對頂點間最短路徑長度 */　　int *nex

26、tvex[];/*存放到最短路徑上的后繼頂點的下標值 */　　} ShortPath;　　Dijkstra算法的實現(xiàn)：　　Void dijksta (GrapMatrix graph,Path *dist){　　int i,j,min;<

27、;p>　　AdjType minw;　　dist[0].length=0;dist[0].prevex=0;graph.arcs[0][0]=1;/*表示頂點在集合U中*/　　for(i=1;i<graph.n;i++){/*初始化集合V-U中頂點的距離值*/　　dist[i].len

28、gth=graph.arcs[0][i];　　if(dist[i].length!=MAX) dist[i].prevex=0;　　else dist[i].prevex=-1;　　}　　for(i=1;i<graph.n;i+

29、+){　　minw=MAX;min=0;　　for(j=1;j<graph.n;j++)　　if((graph.arcs[j][j]==0)&&(dist[j].length<minw))　　minw=dist[j].length;min=j;

30、/*在V-U中選出距離值最小頂點*/　　if(min==0)break;/*從沒有路徑可以通往集合V-U中的頂點*/　　graph.arcs[min][min]=1;/*集合V-U中距離最小值的頂點為MIN*/　　for(j=1;j<graph.n;j++){/

31、*調(diào)整集合V-U中的頂點的最短路徑*/　　if(graph.arcs[j][j]==1)continue;　　if (dist[j].length>dist[min].length+graph.arcs[min][j]){　　dist[j].length=dist[min].length+graph.arc

32、s[min][j];　　dist[j].prevex=min;　　}　　}　　}　　}</b

33、>　　Floyd算法實現(xiàn)：　　Void floyd(GrapMatrix *pgraph,ShortPath *ppath){　　int i,j,k;　　for(i=0;i<pgraph->n;i++)/*初始化 *PPATH */</

34、p>　　for(j=0;j<pgraph->n;j++){　　if(pgraph->arcs[i][j]!=MAX) ppath->nextvex[i][j]=j;　　elseppath->nextvex[i][j]=-1;　　}<

35、/b>　　for(k=0;j<pgraph->n;k++)/*迭代計算 *PPATH */　　for(i=0;i<pgraph->n;i++)　　for(j=0;j<pgraph->n;j++){　　if((ppath

36、->a[i][k]>=MAX)||(ppath->a[k][j]>=MAX)) continue;　　if(ppath->a[i][j]>(ppath->a[i][k]+ppath->a[k][j])){　　ppath->a[i][j]=ppath->a[i][k]+ppath->a[k]

37、[j];　　ppath->nextvex[i][j]=ppath->nextvex[i][k];　　}/*修改 *PPATH */　　}　　}

38、　　四：分析、調(diào)試、測試 　　1．各個算法算法代價分析：　　Dijkstra算法中的初始化部分的時間復雜度為O(N)，求最短路徑部分由一個大循環(huán)組成，其中外循環(huán)N-1次，內(nèi)循環(huán)為兩個，均運行N-1次，因此，算法的時間復雜度為O(),還要注意的是，在算法中如果改變了關(guān)系矩陣中草藥初始狀態(tài)，如果要求算法不能破壞原始數(shù)據(jù)，就需要另外增加數(shù)據(jù)結(jié)

39、構(gòu)記錄。空間代價是0（N）；　　Bellman-Ford算法的時間復雜度為0（VE），其中V=頂點數(shù)，E=邊數(shù) 初始化占用的時間0（V），在對邊進行的V-1趟操作時時間為0（E），因此，算法的時間復雜度為0（VE）；　　Floyd 算法中初始化部分由一個循環(huán)組成，其中外循環(huán)運行N次，內(nèi)循環(huán)也運行N次，初始化部分的時間復雜度為0（N）。迭代成的最短路徑長度

40、矩陣A與路徑矩陣NEXTVEX 的部分，分為三重循環(huán)的嵌套，其時間復雜度為0（N），因此Floyd算法的時間復雜度為0（N）?？臻g代價為0（N）。　　2．算法的比較：　　Dijkstra算法的局限性　　如果邊權(quán)為負值，Dijkstra算法還正確嗎？&l

41、t;p>　　求解下圖A 至其他點的最短距離　　算法步驟：1）標記點A2）Dist[C]=2最小，標記點C3）Dist[B]=3最小，標記點B結(jié)束但是ShortestDist[C]=1　　如果利用Dijkstra算法求解，結(jié)果為……　　標記點A，Dist[B]=-1，標記點B&

42、lt;p>　　Dist[C]=0，標記點C　　Dist[D]=-1，標記點D　　Dist[E]=-2，標記點E　　Dist[F]=-1，標記點F　　所求得的距離并不是最短的。　　Dijkstra的缺陷就在于它不能處理負權(quán)回路

43、：Dijkstra對于標記過的點就不再進行更新了，所以即使有負權(quán)導致最短距離的改變也不會重新計算已經(jīng)計算過的結(jié)果。我們需要新的算法——Bellman-Ford，Bellman-Ford算法基于動態(tài)規(guī)劃，反復用已有的邊來更新最短距離，Bellman-Ford算法的核心思想——松弛。Dist[u]和Dist[v]應當滿足一個關(guān)系，即　　Dist[v]<=Dist[u]+w[u,v]；</

44、p>　?。?）考慮對每條邊進行1次松弛的時候，得到的實際上是至多經(jīng)過0個點的最短路徑，對每條邊進行兩次松弛的時候得到的是至多經(jīng)過1個點的最短路徑，……　?。?）如果沒有負權(quán)回路，那么任意兩點間的最短路徑至多經(jīng)過n-2個點，因此經(jīng)過n-1次松弛操作后應當可以得到最短路徑　?。?）如果有負權(quán)回路，那么第n次松弛操作仍然會成功，這時

45、，最短路徑為-∞　　算法復雜度為O(VE)其中V=頂點數(shù)，E=邊數(shù)　　我們知道Dijkstra的算法復雜度是O(V^2)，經(jīng)過優(yōu)化的Dijkstra算法可以達到O((V+E)logE)　　所以Bellman-Ford算法并不比它快，但實際上Bellman-Ford算法也是可以優(yōu)化的。<

46、;p>　　Bellman-Ford算法的優(yōu)化：　　在沒有負權(quán)回路的時候，至多進行n-1次松弛操作會得到解，但實際上可能不到n-1此松弛操作就得到最優(yōu)解了　　可以在每一輪松弛的時候判斷是否松弛成功，如果所有的邊都沒有松弛的話，說明Bellman-Ford算法已經(jīng)可以結(jié)束了。　　五附錄：<

47、;/b>　　Ｄｉｊｋｓtra算法的完全實現(xiàn)程序：　　#include "stdio.h"　　#include "malloc.h"　　#define maxium 32767　　#de

48、fine maxver 9 /*defines the max number of vertexs which the programm can handle*/　　#define OK 1　　struct Point　　{　　cha

49、r vertex[3];　　struct Link *work;　　struct Point *next;　　};　　struct Link　　{<

50、/p>　　char vertex[3];　　int value;　　struct Link *next;　　};　　struct Table /*the workbannch of the algorith

51、m*/　　{　　int cost;　　int Known;　　char vertex[3];　　char path[3];<

52、p>　　struct Table *next;　　};　　int Dijkstra(struct Point *,struct Table *);　　int PrintTable(int,struct Table *);　　in

53、t PrintPath(int,struct Table *,struct Table *);　　struct Table * CreateTable(int,int);　　struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the

54、smallest value reside in the table*/　　int main()　　{　　int i,j,num,temp,val;　　char c;<

55、;p>　　struct Point *poinpre,*poinhead,*poin;　　struct Link *linpre,*linhead,*lin;　　struct Table *tabhead;　　poinpre=poinhead=poin=(struct Point *)malloc(size

56、of(struct Point));　　poin->next=NULL;　　poin->work=NULL;　　restart:　　printf("Notice:if you wanna to input a v

57、ertex,you must use the format of number!\n");　　printf("Please input the number of points:\n");　　scanf("%d",&num);　　if(num>max

58、ver||num<1||num%1!=0)　　{　　printf("\nNumber of points exception!");　　goto restart;　　}&

59、lt;/p>　　for(i=0;i<num;i++)　　{　　printf("Please input the points next to point %d,end with 0:\n",i+1);　　poin=(str

60、uct Point *)malloc(sizeof(struct Point));　　poinpre->next=poin;　　poin->vertex[0]='v';　　poin->vertex[1]='0'+i+1;

61、　poin->vertex[2]='\0';　　linpre=lin=poin->work;　　linpre->next=NULL;　　for(j=0;j<num-1;j++)　　{</p

62、>　　printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1);　　scanf("%d",&temp);　　if(temp==0)　　{&

63、lt;/b>　　lin->next=NULL;　　break;　　}　　else　　{

64、　　lin=(struct Link *)malloc(sizeof(struct Link));　　linpre->next=lin;　　lin->vertex[0]='v';　　lin->vertex[1]=

65、9;0'+temp;　　lin->vertex[2]='\0';　　printf("Please input the value betwixt %d th point towards %d th point:",i+1,temp);　　scanf("%

66、d",&val);　　lin->value=val;　　linpre=linpre->next;　　lin->next=NULL;　　}

67、　}　　poinpre=poinpre->next;　　poin->next=NULL;　　}　　printf("Please enter the vertex where Dijkstra

68、algorithm starts:\n");　　scanf("%d",&temp);　　tabhead=CreateTable(temp,num);　　Dijkstra(poinhead,tabhead);　　PrintTable(t

69、emp,tabhead);　　return OK;　　}　　struct Table * CreateTable(int vertex,int total)　　{<p

70、>　　struct Table *head,*pre,*p;　　int i;　　head=pre=p=(struct Table *)malloc(sizeof(struct Table));　　p->next=NULL;

71、　　for(i=0;i<total;i++)　　{　　p=(struct Table *)malloc(sizeof(struct Table));　　pre->next=p;　　if(i+1==vertex)</p

72、>　　{　　p->vertex[0]='v';　　p->vertex[1]='0'+i+1;　　p->vertex[2]='\0';　　p-

73、>cost=0;　　p->Known=0;　　}　　else　　{　　p->vertex[0]=&

74、#39;v';　　p->vertex[1]='0'+i+1;　　p->vertex[2]='\0';　　p->cost=maxium;　　p->Known=0;<

75、;b>　　}　　p->next=NULL;　　pre=pre->next;　　}　　return head;　　}&

76、lt;/p>　　int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/　　{　　int costs;　　char temp;<

77、p>　　struct Point *poinhead=p1,*now;　　struct Link *linna;　　struct Table *tabhead=p2,*searc,*result;　　while(1)<b&

78、gt;　　{　　now=FindSmallest(tabhead,poinhead);　　if(now==NULL)　　break;　　result=p2;　　result

79、=result->next;　　while(result!=NULL)　　{　　if(result->vertex[1]==now->vertex[1])　　break;<

80、/p>　　else　　result=result->next;　　}　　linna=now->work->next;　　while(linna!=NU

81、LL) /* update all the vertexs linked to the signed vertex*/　　{　　temp=linna->vertex[1];　　searc=tabhead->next;　　w

82、hile(searc!=NULL)　　{　　if(searc->vertex[1]==temp)/*find the vertex linked to the signed vertex in the table and update*/　　{<

83、/b>　　if((result->cost+linna->value)<searc->cost)　　{　　searc->cost=result->cost+linna->value;/*set the new value*/&l

84、t;/p>　　searc->path[0]='v';　　searc->path[1]=now->vertex[1];　　searc->path[2]='\0';　　}&

85、lt;p>　　break;　　}　　else　　searc=searc->next;　　}

86、;　　linna=linna->next;　　}　　}　　return 1;　　}</

87、p>　　struct Point * FindSmallest(struct Table *head,struct Point *poinhead)　　{　　struct Point *result;　　struct Table *temp;<

88、;/p>　　int min=maxium,status=0;　　head=head->next;　　poinhead=poinhead->next;　　while(head!=NULL)　　{&

89、lt;/p>　　if(!head->Known&&head->cost<min)　　{　　min=head->cost;　　result=poinhead;　　tem

90、p=head;　　status=1;　　}　　head=head->next;　　poinhead=poinhead->next;<b&

91、gt;　　}　　if(status)　　{　　temp->Known=1;　　return result;　　}</p&g

92、t;　　else　　return NULL;　　}　　int PrintTable(int start,struct Table *head)　　{<

93、/b>　　struct Table *begin=head;　　head=head->next;　　while(head!=NULL)　　{　　if((head->verte

94、x[1]-'0')!=start)　　PrintPath(start,head,begin);　　head=head->next;　　}　　return OK;<b

95、>　　}　　int PrintPath(int start,struct Table *head,struct Table *begin)　　{　　struct Table *temp=begin->next,*p,*t;

96、　　p=head;　　t=begin;　　if((p->vertex[1]-'0')!=start&&p!=NULL)　　{

97、;　　while(temp->vertex[1]!=p->path[1]&&temp!=NULL)　　temp=temp->next;　　PrintPath(start,temp,t);　　printf("%s",p->vertex

98、);　　}　　else　　if(p!=NULL)　　printf("\n%s",p->vertex);　　return OK;&

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖頂點間最短路徑算法

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖頂點間最短路徑算法

文檔簡介

溫馨提示

最新文檔

評論

免費下載