這個算法結(jié)構(gòu)很是簡單，但是理解還是有一定的困難，一開始做的時候想不明白，跟著算法自己動手畫畫就知道這個算法具體是怎么回事了。

時間復(fù)雜度是O（N*3）

算法有點(diǎn)動態(tài)規(guī)劃的意思，有兩個數(shù)組，一個（dis[]）是記錄倆頂點(diǎn)之間的最短路徑的長度的，一個[path]數(shù)組是記錄倆結(jié)點(diǎn)的中間結(jié)點(diǎn)的。在初始化這個數(shù)組的默認(rèn)為 頂點(diǎn)的下標(biāo)。。?

最重要的就是下面的幾步

if(dis[sta][end]>dis[sta][temp]+dis[temp][end]){

dis[sta][end] = dis[sta][temp]+dis[temp][end];

}

上面的代碼就是這個算法的精華部分。

sta：開始的頂點(diǎn)，end：結(jié)束的頂點(diǎn)，temp：是sta和end上的中間結(jié)點(diǎn)

兩者相比較，要是有更短的路徑就跟新倆結(jié)點(diǎn)的距離。

以每一個結(jié)點(diǎn)為中間點(diǎn)，更新數(shù)組，也就是所有頂點(diǎn)的距離。

話不多說。上程序。。。。

OK

就這個多，之前的都是鋪墊，注意看重點(diǎn)的部分，floyd算法部分