原文鏈接：https://mp.weixin.qq.com/s/HIeA8Cg4-lEodmH9mIFCRQ
—————? 第二天? —————
小灰的思路如下：
第一步，利用迪杰斯特拉算法的距離表薇正，求出從頂點(diǎn)A出發(fā)柑晒，到其他各個(gè)頂點(diǎn)的最短距離：
第二步欧瘪，繼續(xù)使用迪杰斯特拉算法，求出從頂點(diǎn)B出發(fā)匙赞，到其他各個(gè)頂點(diǎn)的最短距離佛掖。
第三步妖碉，從頂點(diǎn)C出發(fā)，到各個(gè)頂點(diǎn)的最短距離苦囱。
第四步嗅绸，從頂點(diǎn)D出發(fā)......
.......
就像這樣，一直遍歷到頂點(diǎn)G撕彤。
這個(gè)思路的時(shí)間復(fù)雜度是多少呢鱼鸠？
假如圖中有n個(gè)頂點(diǎn)，如果不考慮堆優(yōu)化羹铅，一次迪杰斯特拉算法的時(shí)間復(fù)雜度是O（n^2）蚀狰。所以，把每一個(gè)頂點(diǎn)都計(jì)算一遍职员，總的時(shí)間復(fù)雜度是O（n^3）麻蹋。
舉一個(gè)栗子：
上圖的頂點(diǎn)A和頂點(diǎn)C沒(méi)有直接相連的邊，它們之間的直接距離是無(wú)窮大焊切。
如果以B作為“中繼頂點(diǎn)”扮授，此時(shí)A到C的最短路徑就是A-B-C，最短距離是3+2=5专肪。
再舉一個(gè)栗子：
上圖的頂點(diǎn)A和頂點(diǎn)C直接相連刹勃，距離是6。但是存在一條“迂回”路徑A-B-C嚎尤，距離是3+2=5<6荔仁。
所以，經(jīng)過(guò)中繼頂點(diǎn)B芽死，從A到C的最短距離可以是5乏梁。
下面我們來(lái)看一看Floyd算法的詳細(xì)步驟。
1.要實(shí)現(xiàn)Floyd算法关贵，首先需要構(gòu)建帶權(quán)圖的鄰接矩陣：
在鄰接矩陣當(dāng)中遇骑，每一個(gè)數(shù)字代表著從某個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的直接距離，這個(gè)距離是沒(méi)有涉及到任何中繼頂點(diǎn)的揖曾。
2.此時(shí)假定只允許以頂點(diǎn)A作為中繼頂點(diǎn)质蕉，那么各頂點(diǎn)之間的距離會(huì)變成什么樣子呢？
B和C之間的距離原本是無(wú)窮大翩肌，此時(shí)以A為中繼，距離縮短為AB距離+AC距離=
5+2=7禁悠。
更新對(duì)應(yīng)矩陣元素（橙色區(qū)域代表頂點(diǎn)A到其他頂點(diǎn)的臨時(shí)距離）：
3.接下來(lái)以頂點(diǎn)A念祭、B作為中繼頂點(diǎn)，那么各頂點(diǎn)之間的距離會(huì)變成什么樣子呢碍侦？
A和D之間的距離原本是無(wú)窮大粱坤，此時(shí)以B為中繼隶糕，距離縮短為AB距離+BD距離=5+1=6。
A和E之間的距離原本是無(wú)窮大站玄，此時(shí)以B為中繼枚驻，距離縮短為AB距離+BE距離=5+6=11。
更新對(duì)應(yīng)矩陣元素（橙色區(qū)域代表頂點(diǎn)B到其他頂點(diǎn)的臨時(shí)距離）：
4.接下來(lái)以頂點(diǎn)A株旷、B再登、C作為中繼頂點(diǎn)，那么各頂點(diǎn)之間的距離會(huì)變成什么樣子呢晾剖？
A和F之間的距離原本是無(wú)窮大锉矢，此時(shí)以C為中繼，距離縮短為AC距離+CF距離=2+8=10齿尽。
更新對(duì)應(yīng)矩陣元素（橙色區(qū)域代表頂點(diǎn)C到其他頂點(diǎn)的臨時(shí)距離）：
以此類(lèi)推沽损，我們不斷引入新的中繼頂點(diǎn)，不斷刷新矩陣中的臨時(shí)距離循头。
最終绵估，當(dāng)所有頂點(diǎn)都可以作為中繼頂點(diǎn)時(shí)，我們的距離矩陣更新如下：
此時(shí)卡骂，矩陣中每一個(gè)元素国裳，都對(duì)應(yīng)著某頂點(diǎn)到另一個(gè)頂點(diǎn)的最短距離。
為什么這么說(shuō)呢偿警？讓我們回顧一下動(dòng)態(tài)規(guī)劃的兩大要素：
問(wèn)題的初始狀態(tài)
問(wèn)題的狀態(tài)轉(zhuǎn)移方程式
對(duì)于尋找圖的所有頂點(diǎn)之間距離的問(wèn)題躏救，初始狀態(tài)就是頂點(diǎn)之間的直接距離，也就是鄰接矩陣螟蒸。
而問(wèn)題的狀態(tài)轉(zhuǎn)移方程式又是什么呢盒使？
假設(shè)新引入的中繼頂點(diǎn)是n，那么：
頂點(diǎn)i 到 頂點(diǎn)j 的新距離 = Min（頂點(diǎn)i 到 頂點(diǎn)j 的舊距離七嫌，頂點(diǎn)i 到 頂點(diǎn)n 的距離+頂點(diǎn)n 到 頂點(diǎn)j 的距離）
final static int INF = Integer.MAX_VALUE;
public static void floyd(int[][] matrix){
? ? //循環(huán)更新矩陣的值
? ? for(int k=0; k<matrix.length; k++){
? ? ? ? for(int i=0; i<matrix.length; i++){
? ? ? ? ? ? for(int j=0; j<matrix.length; j++){
? ? ? ? ? ? ? ? if(matrix[i][k] == INF || matrix[k][j] == INF) {
? ? ? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? // 打印floyd最短路徑的結(jié)果
? ? System.out.printf("最短路徑矩陣: \n");
? ? for (int i = 0; i < matrix.length; i++) {
? ? ? ? for (int j = 0; j < matrix.length; j++)
? ? ? ? ? ? System.out.printf("%3d? ", matrix[i][j]);
? ? ? ? System.out.printf("\n");
? ? }
}
public static void main(String[] args) {
? ? int[][] matrix = {
? ? ? ? ? ? {0, 5, 2, INF, INF, INF, INF},
? ? ? ? ? ? {5, 0, INF, 1, 6, INF, INF},
? ? ? ? ? ? {2, INF, 0, 6, INF, 8, INF},
? ? ? ? ? ? {INF, 1, 6, 0, 1, 2, INF},
? ? ? ? ? ? {INF, 6, INF, 1, 0, INF, 7},
? ? ? ? ? ? {INF, INF, 8, 2, INF, 0, 3},
? ? ? ? ? ? {INF, INF, INF, INF, 7, 3, 0}
? ? };
? ? floyd(matrix);
}
【END】
原文鏈接：https://mp.weixin.qq.com/s/HIeA8Cg4-lEodmH9mIFCRQ
讀后感：通常少办，我們習(xí)慣于在已有的知識(shí)范圍內(nèi)去尋找問(wèn)題的解決方法。這個(gè)思路一般來(lái)說(shuō)是沒(méi)錯(cuò)的诵原，但隨著科技的進(jìn)步英妓，今天也許就有比昨天效率更高的方案可以采用。對(duì)于快節(jié)奏的現(xiàn)代生活來(lái)說(shuō)绍赛，效率就等同于效益蔓纠，你能提供越高效的方案，就能給企業(yè)帶來(lái)越高額的利益吗蚌。沒(méi)有了利益腿倚，企業(yè)就生存不下去，如果你不能為企業(yè)的生存和發(fā)展做出比別人更高的貢獻(xiàn)蚯妇，企業(yè)自然不會(huì)選擇你敷燎。所以暂筝，為了生存和發(fā)展的需要，我們要每天學(xué)習(xí)新知識(shí)硬贯，提升自我價(jià)值焕襟。
