內(nèi)容來(lái)自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫(xiě)在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會(huì)偶爾插入自己的注釋和理解，盡量會(huì)完成作業(yè)

這個(gè)不難，加油！堅(jiān)持就是勝利！

14.9.1弗洛伊德算法介紹

1)????? 和Dijkstra算法一樣，弗洛伊德(Floyd)算法也是—種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法。該算法名稱以創(chuàng)始人之一、1978年圖靈獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德命名

2)????? 弗洛伊德算法(Floyd)計(jì)算圖中各個(gè)頂點(diǎn)之間的最短路徑

3)????? 迪杰斯特拉算法用于計(jì)算圖中某一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑。

4)????? 弗洛伊德算法VS迪杰斯特拉算法:迪杰斯特拉算法通過(guò)選定的被訪問(wèn)頂點(diǎn)，求出從出發(fā)訪問(wèn)頂點(diǎn)到其他頂點(diǎn)的最短路徑;弗洛伊德算法中每一個(gè)頂點(diǎn)都是出發(fā)訪問(wèn)點(diǎn)，所以需要將每一個(gè)頂點(diǎn)看做被訪問(wèn)頂點(diǎn)，求出從每一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑。

老韓提示：面試官提問(wèn)佛洛依德和迪杰斯特拉算法的區(qū)別

答：迪杰斯特拉是選一個(gè)頂點(diǎn)，求出這個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑，而弗洛伊德是把每個(gè)頂點(diǎn)都看作出發(fā)頂點(diǎn)，求出到其他頂點(diǎn)的最短路徑

14.9.2弗洛伊德(Floyd)算法圖解分析

1)????? 設(shè)置頂點(diǎn)vi到頂點(diǎn)k的最短路徑已知為L(zhǎng)ik，頂點(diǎn)k到vj的最短路徑已知為L(zhǎng)kj，頂點(diǎn)vi到vj的路徑為L(zhǎng)ij，則vi到vj的最短路徑為: min((Lik+Lkj),Lij)，vk的取值為圖中所有頂點(diǎn)，則可獲得vi到vj的最短路徑

2)????? 至于vi到的最短路徑Lik或者水到vj的最短路徑Lkj，是以同樣的方式獲得

3)????? 弗洛伊德(Floyd)算法圖解分析-舉例說(shuō)明

示例:求最短路徑為例說(shuō)明

弗洛伊德算法的步驟

第一輪循環(huán)中，以A(下標(biāo)為:0)作為中間頂點(diǎn)[即把A作為中間頂點(diǎn)的所有情況都進(jìn)行遍歷就會(huì)更新距離表和前驅(qū)關(guān)系]，距離表和前驅(qū)關(guān)系更新為:

分析如下：

以A頂點(diǎn)作為中間頂點(diǎn)是，B->A->C的距離由N->9，同理C到B;C->A->G的距離由N>12，同理G到C更換中間頂點(diǎn)，循環(huán)執(zhí)行操作，直到所有頂點(diǎn)都作為中間頂點(diǎn)更新后，計(jì)算結(jié)束

14.9.3弗洛伊德(Floyd)算法最佳應(yīng)用-最短路徑

1)????? 勝利鄉(xiāng)有7個(gè)村莊(A,B,C,D,E, F,G)

2)????? 各個(gè)村莊的距離用邊線表示(權(quán))，比如A-B距離5公里

3)????? 問(wèn):如何計(jì)算出各村莊到其它各村莊的最短距離?

代碼實(shí)現(xiàn)：