徹底弄懂最短路徑問題-展示頁
2025-04-03 01:52本頁面
【正文】 oyd算法的基本思想如下：從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過若干個(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)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)K，dist(AB)中記錄的便是A到B的最短路徑的距離。 參考了南陽理工牛帥(目前在新浪)的博客。不知道講得清楚不清楚。3，0，2比如n=3，鄰接矩陣：+Ldmin）,則dmin39。 答案是不能，這與貪心選擇性質(zhì)有關(guān)(ps：貌似還是動(dòng)態(tài)規(guī)劃啊，暈了)，每次都找一個(gè)距源點(diǎn)最近的點(diǎn)（dmin），然后將該距離定為這個(gè)點(diǎn)到源點(diǎn)的最短路徑；但如果存在負(fù)權(quán)邊，那就有可能先通過并不是距源點(diǎn)最近的一個(gè)次優(yōu)點(diǎn)（dmin39。 問題：Dijkstar能否處理負(fù)權(quán)邊？（來自《圖論》） (3)2. 從T中選取一個(gè)其距離值為最小的頂點(diǎn)W(貪心體現(xiàn)在此處)，加入S(注意不是直接從S集合中選取，理解這個(gè)對(duì)于理解vis數(shù)組的作用至關(guān)重要)，對(duì)T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值（上面兩個(gè)并列for循環(huán)，使用最小點(diǎn)更新）。 求最短路徑步驟1. 初使時(shí)令 S={V0},T={其余頂點(diǎn)}，T中頂點(diǎn)對(duì)應(yīng)的距離值， (2) 將T中頂點(diǎn)按最短路徑遞增的次序加入到S中，依據(jù)：可以證明V0到T中頂點(diǎn)Vk的最短路徑，或是從V0到Vk的直接路徑的權(quán)值或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和（反證法可證，說實(shí)話，真不明白哦）。 S：已求出最短路徑的頂點(diǎn)的集合 迪杰斯特拉(Dijkstra)算法按路徑長(zhǎng)度(看下面表格的最后一行，就是next點(diǎn))遞增次序產(chǎn)生最短路徑。 (1) 觀察右邊表格發(fā)現(xiàn)除最后一個(gè)節(jié)點(diǎn)外其他均已經(jīng)求出最短路徑。解決最短路的問題有以下算法，Dijkstra算法，BellmanFord算法，F(xiàn)loyd算法和SPFA算法，另外還有著名的啟發(fā)式搜索算法A*，不過A*準(zhǔn)備單獨(dú)出一篇，其中Floyd算法可以求解任意兩點(diǎn)間的最短路徑的長(zhǎng)度。 我堅(jiān)信：沒有不好的學(xué)生，只有垃圾的教育。我大二的《數(shù)據(jù)結(jié)構(gòu)》是由申老師講的，那時(shí)候不怎么明白，估計(jì)太理論化了(ps：或許是因?yàn)槲宜X了)；今天把老王的2011年課件又看了一遍，給大二的孩子們又講了一遍，隨手谷歌了N多資料，算是徹底搞懂了最短路徑問題。徹底弄懂最短路徑問題 只想說：溫故而知新，可以為師矣。請(qǐng)讀者盡情享用……不過沒有人理所當(dāng)然的對(duì)你好，所以要學(xué)會(huì)感恩。 問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑。筆者認(rèn)為任意一個(gè)最短路算法都是基于這樣一個(gè)事實(shí)：從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過若干個(gè)節(jié)點(diǎn)到B。 該算法在《數(shù)據(jù)結(jié)構(gòu)》課本里是以貪心的形式講解的，不過在《運(yùn)籌學(xué)》教材里被編排在動(dòng)態(tài)規(guī)劃章節(jié)，建議讀者兩篇都看看。先把V分成兩組： VS=T：尚未確定最短路徑的頂點(diǎn)集合若存在V0,Vi，為V0,Vi弧上的權(quán)值（和ＳＰＦＡ初始化方式不同），若不存在V0,Vi，為Inf。3. 重復(fù)上述步驟，直到S中包含所有頂點(diǎn)，即S=V為止（說明最外層是除起點(diǎn)外的遍歷）。 下面是上圖的求解過程，按列來看，第一列是初始化過程，最后一行是每次求得的next點(diǎn)。），再通過這個(gè)負(fù)權(quán)邊L(L0)，使得路徑之和更小（dmin39。+L成為最短路徑，并不是dmin，這樣dijkstra就被囧掉了。0，3，44，2，0,用dijkstra求得d[1，2]=3，事實(shí)上d[1，2]=2，就是通過了132使得路徑減小。 in。 j
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1