在求兩點(diǎn)之間的最短距離最常用的算法：Dijkstra 算法 和 Floyd-Warshall 算法儒士。
1的止、Dijkstra 算法
解決單源有向圖最短路徑問(wèn)題，時(shí)間復(fù)雜度為 O(n2)着撩，n為頂點(diǎn)個(gè)數(shù)诅福，如果是從其他頂點(diǎn)開(kāi)始，那么在原有算法的基礎(chǔ)上再來(lái)一次循環(huán)拖叙，此時(shí)的時(shí)間復(fù)雜度為O(n3)氓润。
特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展(廣度優(yōu)先搜索思想)，直到擴(kuò)展到終點(diǎn)為止薯鳍。
基本思想
通過(guò) Dijkstra 計(jì)算圖G 中的最短路徑時(shí)咖气，需要指定起點(diǎn) s (即從頂點(diǎn) s 開(kāi)始計(jì)算)。
此外，引進(jìn)兩個(gè)集合 S 和 U崩溪。S 的作用是記錄已求出最短路徑的頂點(diǎn)(以及相應(yīng)的最短路徑長(zhǎng)度)浅役，而 U 則是記錄還未求出最短路徑的頂點(diǎn)(以及該頂點(diǎn)到起點(diǎn) s 的距離)。
初始時(shí)悯舟，S 中只有起點(diǎn) s担租；U中是除s之外的頂點(diǎn)砸民，并且U中頂點(diǎn)的路徑是"起點(diǎn) s 到該頂點(diǎn)的路徑"抵怎。然后，從U中找出路徑最短的頂點(diǎn)岭参，并將其加入到 S 中反惕；接著，更新 U 中的頂點(diǎn)和頂點(diǎn)對(duì)應(yīng)的路徑演侯。 然后姿染，再?gòu)腢中找出路徑最短的頂點(diǎn)，并將其加入到 S 中秒际；接著悬赏，更新 U 中的頂點(diǎn)和頂點(diǎn)對(duì)應(yīng)的路徑。 ... 重復(fù)該操作娄徊，直到遍歷完所有頂點(diǎn)闽颇。
代碼實(shí)現(xiàn)：
const INF = Number.MAX_SAFE_INTEGER;
// 查找最近的點(diǎn)
const minDistance = (dist, visited) => {
let min = INF;
let minIndex = -1;
for (let v = 0; v < dist.length; v++) {
if (visited[v] === false && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
};
/**
* @param {圖：鄰接矩陣} graph
* @param {頂點(diǎn)索引} src
*/
export const dijkstra = (graph, src) => {
const dist = [];
// 用于標(biāo)識(shí)頂點(diǎn) src 至其他頂點(diǎn)的距離是否確定
const visited = [];
const { length } = graph;
for (let i = 0; i < length; i++) {
dist[i] = INF;
visited[i] = false;
}
dist[src] = 0;
for (let i = 0; i < length - 1; i++) {
const u = minDistance(dist, visited);
// 標(biāo)識(shí)頂點(diǎn) src 到此頂點(diǎn)的距離已經(jīng)確認(rèn)
visited[u] = true;
for (let v = 0; v < length; v++) {
if (!visited[v] && graph[u][v] !== 0 && dist[u] !== INF && dist[u] + graph[u][v] < dist[v]) {
// 更新 dist
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
};
// test
const graph = [
[0, 2, 4, 0, 0, 0],
[0, 0, 2, 4, 2, 0],
[0, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 2],
[0, 0, 0, 3, 0, 2],
[0, 0, 0, 0, 0, 0]
];
const dist = dijkstra(graph, 0);
for (i = 0; i < dist.length; i++) {
console.log(i + '\t\t' + dist[i]);
}
// result
0 0
1 2
2 4
3 6
4 4
5 6
2、Floyd-Warshall 算法
Floyd-Warshall 算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法寄锐。
解決求所有頂點(diǎn)間的最短路徑問(wèn)題兵多，時(shí)間復(fù)雜度為O(n3)，n為頂點(diǎn)數(shù)橄仆。
可以正確處理有向圖或負(fù)權(quán)的最短路徑問(wèn)題剩膘。
基本思想
要求任意節(jié)點(diǎn) i 到任意節(jié)點(diǎn) j 的最短路徑，假設(shè) Dis(i,j) 為節(jié)點(diǎn) u 到節(jié)點(diǎn) v 的最短路徑的距離盆顾，對(duì)于每一個(gè)節(jié)點(diǎn) k怠褐，我們檢查 Dis(i,k) + Dis(k,j) < Dis(i,j) 是否成立，如果成立您宪，證明從 i 到 k 再到 j 的路徑比 i 直接到 j 的路徑短奈懒，我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來(lái)蚕涤，當(dāng)我們遍歷完所有節(jié)點(diǎn) k筐赔，Dis(i,j)中記錄的便是 i 到 j 的最短路徑的距離。
代碼實(shí)現(xiàn)：
export const floydWarshall = graph => {
const dist = [];
const { length } = graph;
// 初始化鄰接矩陣
for (let i = 0; i < length; i++) {
dist[i] = [];
for (let j = 0; j < length; j++) {
if (i === j) {
dist[i][j] = 0;
} else if (!isFinite(graph[i][j])) {
dist[i][j] = Infinity;
} else {
dist[i][j] = graph[i][j];
}
}
}
for (let k = 0; k < length; k++) {
for (let i = 0; i < length; i++) {
for (let j = 0; j < length; j++) {
// 如果經(jīng)過(guò)下標(biāo)為 k 頂點(diǎn)路徑比原兩點(diǎn)間路徑更短揖铜，當(dāng)前兩點(diǎn)間權(quán)值設(shè)為更小的一個(gè)
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
};
// test
const INF = Infinity;
const graph = [
[INF, 2, 4, INF, INF, INF],
[INF, INF, 2, 4, 2, INF],
[INF, INF, INF, INF, 3, INF],
[INF, INF, INF, INF, INF, 2],
[INF, INF, INF, 3, INF, 2],
[INF, INF, INF, INF, INF, INF]
];
dist = floydWarshall(graph);
let s = '';
for (let i = 0; i < dist.length; ++i) {
s = '';
for (var j = 0; j < dist.length; ++j) {
if (dist[i][j] === INF) s += 'INF ';
else s += dist[i][j] + ' ';
}
console.log(s);
}
// result
0 2 4 6 4 6
INF 0 2 4 2 4
INF INF 0 6 3 5
INF INF INF 0 INF 2
INF INF INF 3 0 2
INF INF INF INF INF 0
參考：
單源最短路徑演示
