Dijkstra算法原理詳細(xì)講解_第1頁(yè)
Dijkstra算法原理詳細(xì)講解_第2頁(yè)
Dijkstra算法原理詳細(xì)講解_第3頁(yè)
Dijkstra算法原理詳細(xì)講解_第4頁(yè)
Dijkstra算法原理詳細(xì)講解_第5頁(yè)
已閱讀5頁(yè),還剩3頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、Dijkstra算法原理詳細(xì)講解如下圖,設(shè)A為源點(diǎn),求A到其他各頂點(diǎn)(B、C、D、E、F)的最短路徑。 線上所標(biāo)注為相鄰線段之間的距離,即權(quán)值。(注:此圖為隨意所畫(huà),其相鄰頂點(diǎn)間的距離與圖中的目視長(zhǎng)度不能一一對(duì)等)算法執(zhí)行步驟如下表:S集合中AbiWs炳景潺役ATMO以A為中I簸,從A開(kāi)嫩球合中怕。a RmAH6A *3中的IS點(diǎn).二8劃UTC=3的J湖短誼入mtnsK。c、&D也粗枳),),ATC0B&H以D力申同點(diǎn), 從ATCT謎醯位 開(kāi)蹴逸入E,此BJS富A C. B,D, !*tWftO2A-M0i-4C=3T*5,R ATCTE =7以E腫間點(diǎn),從ATCTE寸這條觥

2、炳刑g 明) 岫到P&值映力ATCTDTP $發(fā)現(xiàn)HDTP珀瑚為炳6 AFUtB!S=U C. Bf以F供合己如查醍畢ttWit短路注ATM0 ATC=3,ATT 方ATC*6A C匕9枷故命獨(dú)顧IB瞄城1AcutWs=a,c短簽徑ATMO,ATC二3以C為中詞,從AT“3這條狼SJF速入B,此時(shí)S工&C、B牧?xí)rH短格經(jīng)A-HW, ATC,3,ATCThS以B為銅點(diǎn),從ATCTX5這必理V= A TC T45 (比上血* 一殉A晏短)CtW到8枷WA-HT邱ATCTHATC*7ATCTHIAU中的頂冬 8發(fā)現(xiàn)A HTg權(quán)值初t)g _iTlA TC TB TD *(比上面第二扳

3、的A TC TD,6要長(zhǎng))峋到D網(wǎng)更改力ATCTRATCTBTJC眥中的腹點(diǎn)=00溯UTCTDK成值為費(fèi)短i.rV=A KTDTE 4 (比上面第二緇A K H H菱長(zhǎng))岫到E珈賊為 ATCTEm?的發(fā)現(xiàn) ATCT5 權(quán)值為網(wǎng)ATCTET? M2(tt上面算四的ATCTDTP力Dijkstra算法的完整實(shí)現(xiàn)版本之算法的源代碼樣例圖:輸入格式:Turbu C*+ IDEvleAHEiiriiMJL Elie ouRber- fjf gjoints:F|,4I右噬tntt tIw M ntiAbfir af t|i 1*4e insult the uA1114 M mmh” of tlw 2 th

4、 t hi? Vliiu he ifit* 白駐rd氏3i vertex linkedLQ4:5hfrt lyt 4酎polmt t:,MAirdn; 1|1 ho nunhisr of th tlh hefkiiflber of ilk le aac inpji t Ihe he mm her of th I era雷甘inpi t t hp he nLtjn.ber of th1cAHtr input the w.h*爐oft|fep白占匕。iHlMll t. heIbe3 betwixt 2 (Milm土toWflrtis: 3 wrtM linked to ve rtrx 2:4 be

5、 1 wixl 2 Eli |o iAE E awardO- 4VD-rtox Iinkvd to vertex 2:H nrMt to ic! int 1 wit b Rsiwint 1 thvaLum r # (K蛔i3 th t: tM ONIU-輸出格式:thth|M3 iffkt =4k TuEhn d IDEPleaiiB- iniHLt I heU,H i n 11 neMt la pu ini. 9史MH wit h U: The nufibr of tlw 1 th vtrte linked to uorttv 3:5 Plaavfrinput t he vditue bnr

6、twijet 3 th pa int towards th pc int ;4 i he- nikpibvr nf die 2 th vertex inknd to vArtv-x;J* Le-as E 4h|LLL Che lairit s. heitt tx linke! to vertciM 4-3Pleaurt he Vallie4 t)i pa int. t swrctn- 3 t)i |w int: 9The ibimber1of tIMT3 IhUBFLBXlinked La ver-leM 4-SPl4t IniMJit theM-twixt 4 t)i glmt tdwjua

7、 5 tJi point :2I ho nun hr r of tlw 4 th vvrtflx I inked to vcrtoM 41 s 8P I a 1 n 1411 f Iw points n.葛上t峪po int& 電nd. ui h BThe timber of tlw? 1 th vertex 1 inlu*l to yerte-K 5siPleatv inpu.1 I he value betwixt S tli pa Ifkt tdtidrdft & th w Mt:;:;? The nufiliBr of tlNt 2 th urtax jinkt*d t

8、o veteM Sf3Plflnext=NULL;poin-work=NULL;restart:printf(Notice:if you wanna to input a vertex,you must use the format ofnumber!n);printf(Please input the number of points:n);scanf(%d,&num);if(nummaxver|num1|num%1!=0)(printf(nNumber of points exception!);goto restart;for(i=0;inext=poin;poin-vertex

9、0=v;poin-vertex1=0+i+1;poin-vertex2=0;linpre=lin=poin-work;linpre-next=NULL;for(j=0;jnext=NULL; break; else(lin=(struct Link *)malloc(sizeof(struct Link); linpre-next=lin;lin-vertex0=v;lin-vertex1=0+temp;lin-vertex2=0;printf(Please input the value betwixt %d th point towards %d thpoint:,i+1,temp);sc

10、anf(%d,&val); lin-value=val;linpre=linpre-next;lin-next=NULL;poinpre=poinpre-next;poin-next=NULL;printf(Please enter the vertex where Dijkstra algorithm starts:n);scanf(%d”,&temp);tabhead=CreateTable(temp,num);Dijkstra(poinhead,tabhead);PrintTable(temp,tabhead);return OK; struct Table * Crea

11、teTable(int vertex,int total)(struct Table *head,*pre,*p;int i;head=pre=p=(struct Table *)malloc(sizeof(struct Table); p-next=NULL;for(i=0;inext=p;if(i+1=vertex)( p-vertex0=v;p-vertex1=0+i+1;p-vertex2=0;p-cost=0; p-Known=0; else (p-vertex0=v;p-vertex1=0+i+1;p-vertex2=0; p-cost=maxium; p-Known=0; p-n

12、ext=NULL; pre=pre-next; return head; int Dijkstra(struct Point *p1,struct Table *p2)/* Core of the programm*/ (int costs;char temp;struct Point *poinhead=p1,*now;struct Link *linna;struct Table *tabhead=p2,*searc,*result;while(1)(now=FindSmallest(tabhead,poinhead);if(now=NULL) break;result=p2;result

13、=result-next;while(result!=NULL)( if(result-vertex1=now-vertex1) break;else result=result-next; linna=now-work-next;while(linna!=NULL) /* update all the vertexs linked to the signedvertex*/(temp=linna-vertex1; searc=tabhead-next;while(searc!=NULL)( if(searc-vertex1=temp)/*find thevertex linked to th

14、e signed vertex in the table and update*/(if(result-cost+linna-value)cost)( searc-cost=result-cost+linna-value;/*set the new value*/searc-path0=v;searc-path1=now-vertex1;searc-path2=0;break; else searc=searc-next; linna=linna-next;return 1; struct Point * FindSmallest(struct Table*head,struct Point

15、*poinhead) (struct Point *result;struct Table *temp;int min=maxium,status=0;head=head-next;poinhead=poinhead-next;while(head!=NULL)( if(!head-Known&head-costcost;result=poinhead;temp=head;status=1;head=head-next;poinhead=poinhead-next; if(status) (temp-Known=1;return result;elsereturn NULL;int PrintTable(int start,struct Table *head)(struct Table *begin=head;head=head-next;while(head!=NULL)(if(head-vertex1-0)!=start)PrintPath(start,head,begin); head=head-next; return OK; int PrintPath(int start,struct Table*head,struct Table

溫馨提示

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

最新文檔

評(píng)論

0/150

提交評(píng)論