網(wǎng)絡(luò)工程師考點(diǎn)：最短路徑理解筆記

有兩種算法可以實(shí)現(xiàn)，一種是迪杰斯特拉（Dijkstra）算法，一種是弗洛伊德（Floyd）算法。


迪杰斯特拉（Dijkstra）算法：
（給出一個(gè)出發(fā)點(diǎn)，可算出該出發(fā)點(diǎn)到所有其它點(diǎn)的最短距離還有具體路徑）


算法過(guò)程：

一，用D[v]記錄任一點(diǎn)v到出發(fā)點(diǎn)的最短距離，建立一S集合且為空，用以記錄已找出最短距離的點(diǎn)。
二，掃描非S集中D[]值最小的節(jié)點(diǎn)D[w]，也就是找出下一條最短路徑，把節(jié)點(diǎn)w加入S集中。
三，更新所有非S集中的D[]值，看看是否可通過(guò)新加入的w點(diǎn)讓其距離更短：if(D[w]+ < D[v]) then D[v]=D[w]+;
四，跳轉(zhuǎn)到（二）操作，循環(huán)（頂點(diǎn)數(shù)－1）次，依次找出所有頂點(diǎn)的最短路徑。


算法理解：

先證明：下一條最短路徑一定是經(jīng)過(guò)S集中的頂點(diǎn)，或是直接到達(dá)出發(fā)點(diǎn)的。
也就是說(shuō)下一條最短路徑一定不經(jīng)過(guò)S集外的頂點(diǎn)。
證明：如下圖，v為出發(fā)點(diǎn)，假使w為下一條最短路徑的頂點(diǎn)，則一定小于，否則稱k為下一條最短路徑，而不是w，所以 < 則 < 所以w一定通過(guò)S集中的頂點(diǎn)。

第一條最短路徑當(dāng)然是直到出發(fā)點(diǎn)且最短的那條，所以可以掃描初始化后的D[]直接找出最短那條，然后根據(jù)以上證明可得下一條最短路徑一定是通過(guò)剛找出的那條的，由于下一條最短路徑一定是通過(guò)S集的，所有不用每次都掃描所有的路徑，所以只用更新有通過(guò)剛加入的頂點(diǎn)的路徑D[]值（三操作）。再掃描出最短的D[]值，加入S集中（二操作），再更新所有D[]值，依次找出所有頂點(diǎn)。

弗洛伊德（Floyd）算法：
（算出所有每對(duì)頂點(diǎn)間的最短路徑）


算法過(guò)程：

一，用D[v][w]記錄每一對(duì)頂點(diǎn)的最短距離。
二，依次掃描每一個(gè)點(diǎn)，并以其為基點(diǎn)再遍歷所有每一對(duì)頂點(diǎn)D[][]的值，看看是否可用過(guò)該基點(diǎn)讓這對(duì)頂點(diǎn)間的距離更小。

算法理解：

最短距離有三種情況：<