內(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è)

扶正了臉上的痛苦面具，接著干就完事了！

14.8.1應(yīng)用場(chǎng)景-最短路徑問(wèn)題

看一個(gè)應(yīng)用場(chǎng)景和問(wèn)題:

1)????? 戰(zhàn)爭(zhēng)時(shí)期，勝利鄉(xiāng)有7個(gè)村莊(A,B,C,D,E,F,G)﹐現(xiàn)在有六個(gè)郵差，從G點(diǎn)出發(fā)，需要分別把郵件分別送到A,B,C, D,E,F六個(gè)村莊

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

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

4)????? 如果從其它點(diǎn)出發(fā)到各個(gè)點(diǎn)的最短距離又是多少?

?

14.8.2迪杰斯特拉(Dijkstra)算法介紹

迪杰斯特拉(Dijkstra)算法是典型最短路徑算法，用于計(jì)算一個(gè)結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑。它的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展(廣度優(yōu)先搜索思想)，直到擴(kuò)展到終點(diǎn)為止。

?

14.8.3迪杰斯特拉(Dijkstra)算法過(guò)程

1)????? 設(shè)置出發(fā)頂點(diǎn)為v，頂點(diǎn)集合V{v1,v2,wi.}，v到V中各頂點(diǎn)的距離構(gòu)成距離集合Dis，Dis{d1,d2,d...})，Dis集合記錄著v到圖中各頂點(diǎn)的距離(到自身可以看作0，v到vi距離對(duì)應(yīng)為di)

2)????? 從Dis 中選擇值最小的di并移出Dis集合，同時(shí)移出V集合中對(duì)應(yīng)的頂點(diǎn)vi，此時(shí)的v到vi即為最短路徑

3)????? 更新Dis集合，更新規(guī)則為:比較v到V集合中頂點(diǎn)的距離值，與v通過(guò)vi到V集合中頂點(diǎn)的距離值，保留值較小的一個(gè)(同時(shí)也應(yīng)該更新頂點(diǎn)的前驅(qū)節(jié)點(diǎn)為vi，表明是通過(guò)vi到達(dá)的)

4)????? 重復(fù)執(zhí)行兩步驟，直到最短路徑頂點(diǎn)為目標(biāo)頂點(diǎn)即可結(jié)束

14.8.4迪杰斯特拉(Dijkstra)算法最佳應(yīng)用-最短路徑

1)????? 戰(zhàn)爭(zhēng)時(shí)期，勝利鄉(xiāng)有7個(gè)村莊(A,B,C,D,E,F,G)﹐現(xiàn)在有六個(gè)郵差，從G點(diǎn)出發(fā)，需要分別把郵件分別送到A,B,C, D,E,F六個(gè)村莊

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

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

4)????? 如果從其它點(diǎn)出發(fā)到各個(gè)點(diǎn)的最短距離又是多少?

使用圖解的方式分析了迪杰斯特拉(Dijkstra)算法思路

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

兄弟們！學(xué)就完事了，加油！奧里給！