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

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

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

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

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

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

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