文章責編：ak47
看了本文的網(wǎng)友還看了有兩種算法可以實現(xiàn)，一種是迪杰斯特拉（Dijkstra）算法，一種是弗洛伊德（Floyd）算法。
迪杰斯特拉（Dijkstra）算法：
（給出一個出發(fā)點，可算出該出發(fā)點到所有其它點的最短距離還有具體路徑）
算法過程：
一，用D[v]記錄任一點v到出發(fā)點的最短距離，建立一S集合且為空，用以記錄已找出最短距離的點。
二，掃描非S集中D[]值最小的節(jié)點D[w]，也就是找出下一條最短路徑，把節(jié)點w加入S集中。
三，更新所有非S集中的D[]值，看看是否可通過新加入的w點讓其距離更短：if(D[w]+
四，跳轉(zhuǎn)到（二）操作，循環(huán)（頂點數(shù)－1）次，依次找出所有頂點的最短路徑。
算法理解：
先證明：下一條最短路徑一定是經(jīng)過S集中的頂點，或是直接到達出發(fā)點的。
也就是說下一條最短路徑一定不經(jīng)過S集外的頂點。
證明：如下圖，v為出發(fā)點，假使w為下一條最短路徑的頂點，則
第一條最短路徑當然是直到出發(fā)點且最短的那條，所以可以掃描初始化后的D[]直接找出最短那條，然后根據(jù)以上證明可得下一條最短路徑一定是通過剛找出的那條的，由于下一條最短路徑一定是通過S集的，所有不用每次都掃描所有的路徑，所以只用更新有通過剛加入的頂點的路徑D[]值（三操作）。再掃描出最短的D[]值，加入S集中（二操作），再更新所有D[]值，依次找出所有頂點。
弗洛伊德（Floyd）算法：
（算出所有每對頂點間的最短路徑）
算法過程：
一，用D[v][w]記錄每一對頂點的最短距離。
二，依次掃描每一個點，并以其為基點再遍歷所有每一對頂點D[][]的值，看看是否可用過該基點讓這對頂點間的距離更小。
算法理解：
最短距離有三種情況：<
