多源最短路：有向圖，求從每一個頂點到其他所有頂點的最短距離。
假定有向圖的所有點編號為1到n，l[i,j]表示從i到j的邊的長度，如果不存在邊，則置為正無窮。
定義d(k,i,j)表示從點i到點j，并且不經過編號大于k的點的最短距離。
K=0時，d(0,i,j)=l[i,j]。
d(k,i,j)=min{ d(k⑴,i,j)，d(k⑴,i,k)+d(k⑴,k,j) } 1<=k<=n
因而我們有以下的遞歸式：
明顯，Floyd算法的時間復雜度是Θ(n3)，空間復雜度是Θ(n2)。
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
