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

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

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

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

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