糯米

    floyd算法是一個經(jīng)典的動態(tài)規(guī)劃算法。用通俗的語言來描述的話，首先我們的目標是尋找從點i到點j的最短路徑。從動態(tài)規(guī)劃的角度看問題，我們需要為這個目標重新做一個詮釋（這個詮釋正是動態(tài)規(guī)劃最富創(chuàng)造力的精華所在），floyd算法加入了這個概念

    A^k(i,j)：表示從i到j中途不經(jīng)過索引比k大的點的最短路徑。

    這個限制的重要之處在于，它將最短路徑的概念做了限制，使得該限制有機會滿足迭代關系，這個迭代關系就在于研究：假設A^k(i,j)已知，是否可以借此推導出A^k-1(i,j)。

    假設我現(xiàn)在要得到A^k(i,j)，而此時A^k(i,j)已知，那么我可以分兩種情況來看待問題：1. A^k(i,j)沿途經(jīng)過點k；2. A^k(i,j)不經(jīng)過點k。如果經(jīng)過點k，那么很顯然，A^k(i,j) = A^k-1(i,k) + A^k-1(k,j)，為什么是A^k-1呢？因為對(i,k)和(k,j)，由于k本身就是源點（或者說終點），加上我們求的是A^k(i,j)，所以滿足不經(jīng)過比k大的點的條件限制，且已經(jīng)不會經(jīng)過點k，故得出了A^k-1這個值。那么遇到第二種情況，A^k(i,j)不經(jīng)過點k時，由于沒有經(jīng)過點k，所以根據(jù)概念，可以得出A^k(i,j)=A^k-1(i,j)。現(xiàn)在，我們確信有且只有這兩種情況---不是經(jīng)過點k，就是不經(jīng)過點k，沒有第三種情況了，條件很完整，那么是選擇哪一個呢？很簡單，求的是最短路徑，當然是哪個最短，求取哪個，故得出式子：

    A^k(i,j) = min( A^k-1(i,j), A^k-1(i,k) + A^k-1(k,j) )