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