今天在幫圈子裡一位朋友規劃第七層網絡路徑規劃的時候，又一次遇到了最短路徑算法的問題，我不想在這裡貼Dijkstra算法或者Floyd算法的源碼，也不想去刻意分辨什麼動態規劃和貪心算法的聯系和區別，只是閒來記錄幾筆而已。鑒於之前寫了很多關於TCP/IP網絡的文章且專業性都比較強，自然的，其可讀性和可查閱性就會很弱，所以，關於本文，我想寫的隨意一些。
-----------------------------------
2009年，由於工作原因第一次用到了Dijkstra算法，非常順利，直接在網上找了一段代碼...但是我下班後卻沒有直接回家，而是直接跑去了上海書城五樓東北角的書架上再次翻閱了一本關於算法的書，尋找Dijkstra算法正確性的證明。之所以我知道這本書裡有這個證明並且能在正確的位置找到它，原因不外乎以下兩點：第一，我之前看到過這個證明，但是由於沒有真正用到，所以一掃而過，第二，這種問題足夠重要但關注的人又比較少，所以那本書可以一直在那裡而不被下架或者售罄。
好吧，我承認那個時候我真正看懂了Dijkstra算法的證明，並且在幾年後的2015年的一天由於又一次遇到了相關的問題還寫了一篇博客。今天，當我再次遇到相關問題的時候，我自然而然地又一次想起了上海書城和我的那篇博客，但我首先已經不可能再跑去上海書城了，我目前人在深圳...再看那篇博客，我發現寫的是如此亂七八糟，以至於我想刪掉它！所以，我想再來一篇！
我們需要求的是從S到D的最短路徑，怎麼證明按照Dijkstra算法一步步操作，最終的結果就一定正確呢？其實很簡單，我也不再去扯什麼數學歸納法之類的了，我試著用平和的自然語言去闡述這個問題。
首先我們要承認從S到D的最短路徑是一定存在的，然後我們用執果溯因法，假設已經找到了這條路徑，它是S-a-b-c-d-e-...-D。那麼以下結論是可以證明的，那就是：
S到a的最短路徑就是S-a；
S到b的最短路徑就是S-a-b
S到c的最短路徑就是S-a-b-c
...
想證明以上這些非常簡單，那就是利用松弛算法，假設S到a的最短路徑不是S-a，而是經過了其它的節點，比如A'，那麼很顯然S-A'-a的長度小於S-a，因此就會得出從S到D的最短路徑是S-A'-a-b-c-d-e-...-D而不是S-a-b-c-d-e-...-D，這與假設是違背的。
類似的，我們可以證明以上其它的結論也是正確的。
接下來的結論就是，只要按照最短路徑每次加進一段，當這些路徑中節點包含D的時候，就可以堅定地說，我找到了從S到D的最短路徑。現在的問題是，如何證明Dijkstra算法每次加入的那個節點x算出的從S到x的距離就是S到x的最短距離。
這也很簡單，假設不是最短距離會怎樣呢？也就是說，如果x通過另一個節點y到達S的距離更短，會怎樣呢？如果這樣的話，Dijkstra算法根本就不會選擇x加入已經確定的集合，而會選擇y節點加入，所以這是矛盾的！
...
把一個復雜的全局性的問題，執果溯因法分解到簡單的單體問題，然後只需證明算法針對單體問題是正確的，就一切OK了。
我覺得，我以上的解釋要比之前那篇證明Dijkstra算法正確性的博客更加容易理解吧。
好了，當我們知道了Dijkstra算法是正確的，接下來呢？
-----------------------------------
事實上，對於大多數的學生或者領域內的工作者而言，根本沒有必要去操心Dijkstra算法正確與否，直接拿來用即可，只有事多的較真兒的或者美其名曰研究型的人才會關注算法的正確性。相反，令人悲哀的是，對於大多數的人而言，看我上面的論述，不如直接來一段可以編譯通過並打印出結果的C代碼或者Java代碼來的痛快。對於我個人而言，也一樣，我自己也想來點可操作的東西，我不想或者說是十分討厭在操作之外空談理論。那麼，我該來一段Dijkstra算法的代碼嗎？
不！決不！
接下來的篇幅交給另一個算法，即Floyd算法。這次，我只談操作性，不談證明。
事實上，我並沒刻意去區分Floyd算法和Dijkstra算法，它們本質上是一樣的東西，都是局部決定整體思想下的結果。
首先將一個原始圖轉化為以下兩個矩陣，其中矩陣D表示圖的鄰接矩陣，而矩陣P表示圖節點的經由路徑：
然後操作就開始了，步驟非常之簡單，我只給出前三個步驟：
五個步驟操作全部完成後，矩陣D的結果代表的就是節點間的最短距離，而矩陣P則表示一張路由表，這兩個矩陣代表了一個任意節點到任意節點間最短路徑的向量集，是的，它是一張完美的路由表。
這個Floyd算法是個典型的Step by Step的算法步驟，非常適合計算機硬件去實現，但是相對於單源Dijkstra算法，其時間復雜度是立方級的O(n^3)，對於路由器而言，這實則壓力不小，反觀Dijkstra算法則更適合路由器，因為IP網絡是逐跳轉發的，路由器只用操心以自己為源點到達其它任意節點的最短距離即可。
-----------------------------------
幫朋友做的這個事涉及到了一些地圖和導航的東西，第七層路由是一個很泛的概念，你可以將它看作是任何只要不是TCP/IP或者其以下的層面的最短路徑規劃問題。事實上，這個所謂的第七層路由在CDN回源以及源站之間的同步方面起著很大的作用。路由本身就不單指IP路由，它的含義是”你要經由的路徑“。
-----------------------------------
自小就對地圖感興趣，小時候沒事就買地圖冊來看，只要是可以做把點用線連起來的事，我都特別感興趣，比如說除了地圖，我還喜歡針線活兒，家裡大大小小的針線活都是我來做，當然，縫補是十分講技巧的，每一個針腳都要斟酌，如何用最少的線，如何不留痕跡等等...另外，我喜歡走街竄巷，不為去什麼目的地，只是走走看看但是絕對不停...後來，我接觸到了圖論，發現這一切的背後都是有理論基礎的，這也許就是後來上學後我非常喜歡網絡技術的原因吧，同時這也是我討厭TCP的原因，因為我看不到把端節點連起來的那根線(我喜歡獅子，獵豹和貓，但我討厭鬣狗，禿鹫和蝙蝠)。
我曾經很驚奇於自己為什麼可以不用導航每次都可以在節假日避開擁堵的路段(我被家人和很多朋友稱作活導航)，後來我想通了，之所以我每次都可以避開擁堵，並不是因為我有什麼特異功能，而是因為他們其它人大多數都使用了導航，而我要說的是，這些導航無一例外都是垃圾！我罵它們是垃圾並沒有待價而沽而欲求職的念頭，我現在已經有一份很好的工作，並且短期內不會更換，完全不是為了受到青睐而罵它們垃圾，這完全是因為這些導航做的本來就是垃圾！
即便再過一年，我突然想換一份工作了，我也依然不會待價而沽，我為什麼不在自己的公司的另一個部門換一個職位呢？求別騷擾！但我還是忍不住想說所有的導航都是垃圾！本來我想多寫點關於導航尋址的事情的，這也不枉本文的題目，然而老婆和小小下周要回上海，周日我要陪她們，所以就不熬了。
-----------------------------------
《JAVA編程思想》裡有思想嗎？編程需要思想嗎？難道不是照著經理的指示做就可以了嗎？是的，編程不需要思想，編程只需要照著經理的指示做即可。現在，問題不在這裡，現在的問題是，就算經理死了，那麼《JAVA編程思想》裡有思想嗎？不！還是沒有思想！你能在《JAVA編程思想》這本書裡看到什麼思想嗎？除了講語法和注意事項之外，你能看到《紅樓夢》般的思想嗎？不，你不能！
所以，《JAVA編程思想》沒思想。Together with 溫州皮鞋廠老板和經理是傻逼，被爆菊！
