有兩種算法可以實現，一種是迪杰斯特拉（Dijkstra）算法，一種是弗洛伊德（Floyd）算法。


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


算法過程：

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


算法理解：

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

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

弗洛伊德（Floyd）算法：
（算出所有每對頂點間的最短路徑）


算法過程：

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

算法理解：

最短距離有三種情況：<