徹底弄懂最短路徑問(wèn)題-wenkub
2023-04-09 01:52:56 本頁(yè)面
【正文】 ext點(diǎn)。3. 重復(fù)上述步驟，直到S中包含所有頂點(diǎn)，即S=V為止（說(shuō)明最外層是除起點(diǎn)外的遍歷）。 VS=T：尚未確定最短路徑的頂點(diǎn)集合 該算法在《數(shù)據(jù)結(jié)構(gòu)》課本里是以貪心的形式講解的，不過(guò)在《運(yùn)籌學(xué)》教材里被編排在動(dòng)態(tài)規(guī)劃章節(jié)，建議讀者兩篇都看看。筆者認(rèn)為任意一個(gè)最短路算法都是基于這樣一個(gè)事實(shí)：從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過(guò)若干個(gè)節(jié)點(diǎn)到B。 只想說(shuō)：溫故而知新，可以為師矣。徹底弄懂最短路徑問(wèn)題我大二的《數(shù)據(jù)結(jié)構(gòu)》是由申老師講的，那時(shí)候不怎么明白，估計(jì)太理論化了(ps：或許是因?yàn)槲宜X(jué)了)；今天把老王的2011年課件又看了一遍，給大二的孩子們又講了一遍，隨手谷歌了N多資料，算是徹底搞懂了最短路徑問(wèn)題。 我堅(jiān)信：沒(méi)有不好的學(xué)生，只有垃圾的教育。 迪杰斯特拉(Dijkstra)算法按路徑長(zhǎng)度(看下面表格的最后一行，就是next點(diǎn))遞增次序產(chǎn)生最短路徑。 求最短路徑步驟1. 初使時(shí)令 S={V0},T={其余頂點(diǎn)}，T中頂點(diǎn)對(duì)應(yīng)的距離值， 問(wèn)題：Dijkstar能否處理負(fù)權(quán)邊？（來(lái)自《圖論》） 答案是不能，這與貪心選擇性質(zhì)有關(guān)(ps：貌似還是動(dòng)態(tài)規(guī)劃啊，暈了)，每次都找一個(gè)距源點(diǎn)最近的點(diǎn)（dmin），然后將該距離定為這個(gè)點(diǎn)到源點(diǎn)的最短路徑；但如果存在負(fù)權(quán)邊，那就有可能先通過(guò)并不是距源點(diǎn)最近的一個(gè)次優(yōu)點(diǎn)（dmin39。比如n=3，鄰接矩陣：不知道講得清楚不清楚。 參考了南陽(yáng)理工牛帥(目前在新浪)的博客。 Floyd算法的基本思想如下：從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過(guò)若干個(gè)節(jié)點(diǎn)到B，所以，我們假設(shè)dist(AB)為節(jié)點(diǎn)A到節(jié)點(diǎn)B的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)K，我們檢查dist(AK) + dist(KB) dist(AB)是否成立，如果成立，證明從A到K再到B的路徑比A直接到B的路徑短，我們便設(shè)置 dist(AB) = dist(AK) + dist(KB)，這樣一來(lái)，當(dāng)我們遍歷完所有節(jié)點(diǎn)K，dist(AB)中記錄的便是A到B的最短路徑的距離。 很簡(jiǎn)單吧，代碼看起來(lái)可能像下面這樣：for (int i=0。 ++j) { for (int k=0。所以，我們需要改寫循環(huán)順序，如下：for (int k=0。 ++i) { for (int j=0。 } } }}半個(gè)小時(shí)足矣（早知道的話會(huì)節(jié)省很多個(gè)半小時(shí)了。 i=n 。//表示 i j 不通 }else{ path[i][j] = i。 i=n。amp。 } } } } } void printPath(int from, int to) { /* * 這是倒序輸出，若想正序可放入棧中，然后輸出。因此，如果G中包含邊i, j，則c[i, j, 0] =邊i, j 的長(zhǎng)度；若i= j ，則c[i,j,0]=0；如果G中不包含邊i, j，則c (i, j, 0)= +∞。c[i, j, k]可取兩者中的最小值。 //國(guó)家名 //貨幣兌換數(shù)FrenchFranc USDollar下面就是floyd算法啦，初始化其它點(diǎn)為1，對(duì)角線為1，采用乘法更新求最大值。 為了能夠求解邊上帶有負(fù)值的單源最短路徑問(wèn)題，Bellman(貝爾曼，動(dòng)態(tài)規(guī)劃提出者)和Ford(福特)提出了從源點(diǎn)逐次繞過(guò)其他頂點(diǎn)，以縮短到達(dá)終點(diǎn)的最短路徑長(zhǎng)度的方法。Bellmanford算法有一個(gè)小優(yōu)化：每次松弛先設(shè)一個(gè)flag，初值為FALSE，若有邊更新則賦值為TRUE，最終如果還是FALSE則直接成功退出。Bellman算法在求解過(guò)程中，每次循環(huán)都要修改所有
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1