本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。

ospf協(xié)議很多人都知道，很多人也會(huì)配置而且很熟練，但是很少有人懂得其背后的思想是什么，Dijkstra算法是求解單源最短路徑的絕妙算法之一，我打心眼里頭喜歡這個(gè)算法，真想把之一去掉。Dijkstra算法是一種貪心算法，貪心算法的本質(zhì)就是最值的和還是最值，也就是說(shuō)人們相信我只要在點(diǎn)滴當(dāng)中盡自己最大的努力，那么最后的結(jié)果就是最好的，可能你會(huì)說(shuō)不一定，但是你敢說(shuō)如果有一個(gè)環(huán)節(jié)你沒(méi)有盡最大的努力，最后的結(jié)果會(huì)更好嗎？你不能，我也不能，因?yàn)楝F(xiàn)實(shí)總是很殘酷，事后諸葛亮只能出現(xiàn)在理想狀態(tài)，事情已經(jīng)發(fā)生，那么你就不能說(shuō)更好的結(jié)果需要什么條件，正所謂“證明一件事是錯(cuò)的很容易，但是證明一件事正確根本不可能！”，因此貪心算法的證明非常復(fù)雜，可是dijkstra算法確實(shí)是正確的，為什么？不是因?yàn)樗皇羌兇獾呢澬乃惴�，正是因�(yàn)樗臈l件里面存在的信息很少，我們可以利用另一把利器來(lái)證明之，這把利器就是“數(shù)學(xué)歸納法”。

數(shù)學(xué)歸納法是一種藝術(shù)，玩過(guò)多米諾骨牌的都知道，要使得任意數(shù)量的所有牌全部翻掉需要兩個(gè)條件而且只需要兩個(gè)條件，一個(gè)就是任意兩張牌間隔足夠近，另一個(gè)條件就是你必須推到第一張牌，就是這么簡(jiǎn)單。于是如果你往這個(gè)游戲靠攏你會(huì)發(fā)現(xiàn)，牌的倒掉和牌的數(shù)量以及牌上的內(nèi)容沒(méi)有任何關(guān)系，那么任何可以歸結(jié)到這個(gè)游戲的數(shù)學(xué)模型都可以用這個(gè)原理進(jìn)行求解，多米諾骨牌游戲的數(shù)學(xué)模型就是數(shù)學(xué)歸納法，數(shù)學(xué)歸納法進(jìn)行的證明需要兩點(diǎn)，第一就是初始條件（推到第一張牌），第二就是假設(shè)n成立證明n+1成立（兩張牌間隔足夠近），貪心算法是一個(gè)步驟問(wèn)題，如果我們可以證明貪心算法的第一部很顯然正確并且在歸納假設(shè)的情況下證明歸納假設(shè)的系一個(gè)步驟也正確的話，那么貪心算法的局部最優(yōu)解結(jié)合成的全局解一定是全局最優(yōu)解，這是一定的。

Dijkstra算法是一個(gè)貪心算法，那么我們可以通過(guò)數(shù)學(xué)歸納法證明其正確性，關(guān)鍵就是如何建立數(shù)學(xué)模型。Dijkstra算法的步驟是顯然的，是簡(jiǎn)單的，我們只需要證明這個(gè)算法產(chǎn)生的路徑就是最短的就可以了，于是模型就有了，很多書(shū)上都用open-set作為“外面”的點(diǎn)，將close-set作為加入到“里面”的點(diǎn)，那么我們就證明每通過(guò)dijkstra算法加入到close-set的點(diǎn)到原點(diǎn)的距離就是到原點(diǎn)距離的最短距離，這樣我們就證明了算法本身的正確性，因此開(kāi)始用數(shù)學(xué)歸納法證明吧，當(dāng)close-set中除了原點(diǎn)只有一個(gè)點(diǎn)的時(shí)候，這個(gè)點(diǎn)p離原點(diǎn)s的距離一定是最短的，因?yàn)槿绻鹲先到x再到p的距離比s直接到p還短，那么s到x會(huì)更短，算法就不會(huì)選中p而會(huì)選中x，與假設(shè)矛盾，這里已經(jīng)證明了初始條件，下面開(kāi)始?xì)w納假設(shè)，設(shè)close-set中有k個(gè)點(diǎn)時(shí)，所有close-set中的k個(gè)點(diǎn)根據(jù)算法算出的距離都是最短的距離，那么我們考慮加入第k+1個(gè)點(diǎn)加入時(shí)的情形，只要能證明k+1個(gè)點(diǎn)按照算法加入進(jìn)close-set從而算出的距離也是最短距離的話，那么問(wèn)題得證，這個(gè)問(wèn)題也是很好證明的，同樣用反證法，假設(shè)不是靠算法加入的，那么路徑中一定除了終點(diǎn)p之外還有一個(gè)點(diǎn)在open-set中，如果這樣的話，根本就不可選中終點(diǎn)p而會(huì)選中那個(gè)經(jīng)過(guò)的點(diǎn)，也是矛盾的，由此問(wèn)題得證。在上面額證明中，所有在close-set中和p相連的點(diǎn)都會(huì)參與最后的最短距離競(jìng)爭(zhēng)，因此就在它們當(dāng)中選一條路徑最為結(jié)果就是問(wèn)題的答案，而這正是算法的行為。

這里可以看到有時(shí)候貪心算法可以用數(shù)學(xué)歸納法來(lái)證明，但是有的時(shí)候不能，不能的原因就在于約束條件太多，要么就是因?yàn)槌跏紬l件無(wú)法被證明但是歸納假設(shè)卻正確，，其實(shí)千萬(wàn)不要過(guò)度懷疑貪心算法，我們?nèi)俗鍪碌臅r(shí)候不是也都是在用貪心算法嗎？如果有誰(shuí)在做事之前來(lái)個(gè)全局證明或者必須證明其嚴(yán)密性的話，那么這個(gè)人最終會(huì)因?yàn)槔碇沁^(guò)度要么被社會(huì)淘汰，要么成為劃時(shí)代的思想家。貪心算法來(lái)自于一個(gè)事實(shí)，那就是爆炸，爆炸波的包絡(luò)面總是呈球面向外擴(kuò)撒，球面剛接觸到一個(gè)點(diǎn)的時(shí)候，這個(gè)點(diǎn)到爆炸源的距離肯定最短，這不是廢話嗎？這個(gè)點(diǎn)到爆炸源的連線不是一條線段嗎？很多的時(shí)候是一條線段，但是考慮到爆炸不是在一個(gè)密度相同的沒(méi)有障礙物的地方，而是在一個(gè)建筑物里面，該建筑物內(nèi)部有復(fù)雜的小隔間，而且各個(gè)隔間相通，隔間之間是堅(jiān)固的鋼板隔開(kāi)，爆炸無(wú)法摧毀這些隔板，那么爆炸波的包絡(luò)面雖然是球面，但是實(shí)際路線卻不是線段，而是沿著各個(gè)隔間之間的通道走的，這個(gè)時(shí)候首先被波及的點(diǎn)沿著爆炸波的路線回到爆炸點(diǎn)，路線肯定是最短的，這是事實(shí)啊，好事怎么也波及不到我們，壞事總是用最快的是速度到來(lái)。

有時(shí)候覺(jué)得人做事很多時(shí)候挺像計(jì)算機(jī)的，用了很多的算法，按經(jīng)驗(yàn)步驟進(jìn)行，不求甚解，而我們從小學(xué)開(kāi)始學(xué)的那些數(shù)學(xué)，比如解方程，函數(shù)求導(dǎo)之類(lèi)的卻是純思維的東西，這些一般來(lái)用發(fā)掘新的算法，人的算法還來(lái)自于經(jīng)驗(yàn)，但是到底哪個(gè)更重要呢？

  本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。