徹底弄懂最短路徑問(wèn)題(編輯修改稿)
2025-04-21 01:52 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 } } } } void printPath(int from, int to) { /* * 這是倒序輸出，若想正序可放入棧中，然后輸出。 * * 這樣的輸出為什么正確呢？個(gè)人認(rèn)為用到了最優(yōu)子結(jié)構(gòu)性質(zhì)， * 即最短路徑的子路徑仍然是最短路徑 */ while(path[from][to]!=from) { (path[from][to] +)。 to = path[from][to]。 } } 《數(shù)據(jù)結(jié)構(gòu)》課本上的那種方式我現(xiàn)在還是不想看，看著不舒服…… Floyd算法另一種理解DP，為理論愛(ài)好者準(zhǔn)備的，上面這個(gè)形式的算法其實(shí)是Floyd算法的精簡(jiǎn)版，而真正的Floyd算法是一種基于DP(Dynamic Programming)的最短路徑算法。設(shè)圖G中n 個(gè)頂點(diǎn)的編號(hào)為1到n。令c [i, j, k]表示從i 到j(luò) 的最短路徑的長(zhǎng)度，其中k 表示該路徑中的最大頂點(diǎn)，也就是說(shuō)c[i,j,k]這條最短路徑所通過(guò)的中間頂點(diǎn)最大不超過(guò)k。因此，如果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, n] 則是從i 到j(luò) 的最短路徑的長(zhǎng)度。對(duì)于任意的k0，通過(guò)分析可以得到：中間頂點(diǎn)不超過(guò)k 的i 到j(luò) 的最短路徑有兩種可能：該路徑含或不含中間頂點(diǎn)k。若不含，則該路徑長(zhǎng)度應(yīng)為c[i, j, k1]，否則長(zhǎng)度為 c[i, k, k1] +c [k, j, k1]。c[i, j, k]可取兩者中的最小值。狀態(tài)轉(zhuǎn)移方程：c[i, j, k]=min{c[i, j, k1], c [i, k, k1]+c [k, j, k1]}，k＞0。這樣，問(wèn)題便具有了最優(yōu)子結(jié)構(gòu)性質(zhì)，可以用動(dòng)態(tài)規(guī)劃方法來(lái)求解。 看另一個(gè)DP(直接引用王老師課件) 說(shuō)了這么多，相信讀者已經(jīng)躍躍欲試了，咱們看一道例題，以ZOJ 1092為例：給你一組國(guó)家和國(guó)家間的部分貨幣匯率兌換表，問(wèn)你是否存在一種方式，從一種貨幣出發(fā)，經(jīng)過(guò)一系列的貨幣兌換，最后返回該貨幣時(shí)大于出發(fā)時(shí)的數(shù)值(ps：這就是所謂的投機(jī)倒把吧)，下面是一組輸入。3 //國(guó)家數(shù)USDollar //國(guó)家名BritishPoundFrenchFranc 3 //貨幣兌換數(shù)USDollar BritishPound //部分貨幣匯率兌換表BritishPound FrenchFrancFrenchFranc USDollar 月賽做的題，不過(guò)當(dāng)時(shí)用的思路是求強(qiáng)連通分量(ps：明明說(shuō)的，那時(shí)我和華杰感覺(jué)好有道理)，也沒(méi)做出來(lái)，現(xiàn)在知道了直接floyd算法就ok了。 思路分析：輸入的時(shí)候可以采用MapString,Integer map = new HashMapString,Integer()主要是為了獲得再次包含匯率輸入時(shí)候的下標(biāo)以建圖(感覺(jué)自己寫(xiě)的好拗口)，或者第一次直接存入String數(shù)組str，再次輸入的時(shí)候每次遍歷str數(shù)組，若是equals那么就把str的下標(biāo)賦值給該幣種建圖。下面就是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算法是求含負(fù)權(quán)圖的單源最
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1