最短路徑學(xué)年論文-wenkub
2023-07-11 05:23:57 本頁(yè)面
【正文】 即費(fèi)用最省。 Dijkstra算法舉例 問(wèn)題的提出，給定一個(gè)帶權(quán)有向圖（既有向網(wǎng)）G和源點(diǎn)Vo，求Vo到G中其他每個(gè)頂點(diǎn)的最短路徑。Dijkstra算法每次從V—S中取出具有最短路徑長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)短路徑進(jìn)行修改。其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地做貪心選擇來(lái)擴(kuò)充這個(gè)集合。為了求出賦權(quán)圖中任意兩結(jié)點(diǎn)之間的最短路徑,通常采用兩種方法。 最短路問(wèn)題常見(jiàn)算法在求解網(wǎng)絡(luò)圖上節(jié)點(diǎn)間最短路徑的方法中,目前國(guó)內(nèi)外一致公認(rèn)的較好算法有迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法。定義1若圖G=G(V,E)中各邊e都賦有一個(gè)實(shí)數(shù)W(e),稱(chēng)為邊e的權(quán),則稱(chēng)這種圖為賦權(quán)圖,記為G=G(V,E,W)。后來(lái)海斯在Dijkstra算法的基礎(chǔ)之上提出了海斯算法。最短路不僅僅指一般地理意義上的距離最短,還可以引申到其它的度量,如時(shí)間、費(fèi)用、線路容量等。118 論文總結(jié)116 利用計(jì)算機(jī)程序模擬算法74 Floyd算法323 Dijkstra算法摘要：主要介紹最短路徑問(wèn)題中的經(jīng)典算法——迪杰斯特拉(Dijkstra)算法和弗洛伊德（Floyd）算法，以及在實(shí)際生活中的運(yùn)用。11引言27117 附錄最短路徑算法的選擇與實(shí)現(xiàn)是通道路線設(shè)計(jì)的基礎(chǔ),最短路徑算法是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域的研究熱點(diǎn),很多網(wǎng)絡(luò)相關(guān)問(wèn)題均可納入最短路徑問(wèn)題的范疇之中。但這兩種算法都不能解決含有負(fù)權(quán)的圖的最短路問(wèn)題。定義2若圖G=G(V,E)是賦權(quán)圖且,假設(shè)[i,j] 的權(quán)記為,若i與j之間沒(méi)有邊相連接，那么。這兩種算法中,網(wǎng)絡(luò)被抽象為一個(gè)圖論中定義的有向或無(wú)向圖,并利用圖的節(jié)點(diǎn)鄰接矩陣記錄點(diǎn)間的關(guān)聯(lián)信息。一種方法是每次以一個(gè)結(jié)點(diǎn)為源點(diǎn),重復(fù)執(zhí)行Dijkstra算法n次。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。一旦S包含了所有V中頂點(diǎn)，那么最后記錄的最短路徑就是源到所有其他頂點(diǎn)之間的最短路徑長(zhǎng)度。：12555581022 圖1 公路網(wǎng)絡(luò)賦權(quán)圖為了方便計(jì)算,先作出該網(wǎng)絡(luò)的距離鄰接矩陣,如下:設(shè),第一次迭代①計(jì)算如下②取,令③由于,令轉(zhuǎn)(1)第二次迭代:①算如下②取令③由于,令轉(zhuǎn)(1)第三次迭代:①算如下②?、塾捎?令轉(zhuǎn)(1)第四次迭代:①算如下②取③由于,令轉(zhuǎn)(1)第五次迭代:①算如下②由于。Dijkstra算法是貪心算法策略的一個(gè)典型例子。此為矛盾。將添加u之前的S成為老S。如果這條新特殊路徑經(jīng)過(guò)老S到達(dá)u后，不是從u經(jīng)過(guò)一條邊直接到達(dá)i，而是像圖3那樣，回到老S中某個(gè)頂點(diǎn)x，最后才到達(dá)頂點(diǎn)i，那么由于x在老S中，因此x比u先加入S，所以圖3中從源到x的路的長(zhǎng)度比從源到u，再?gòu)膗到x的路的長(zhǎng)度小。
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1