Floyd演算法
一個號稱只有5行代碼的演算法， 由1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。該演算法有於求一個帶權有向圖(Wighted Directed Graph)的任意兩點的最短距離的演算法，運用了動態規劃的思想, 演算法的時間複雜度為O(V^3)，空間複雜度O(V^2)。
其核心思想是，在兩個頂點之間插入一個或一個以上的中轉點，比較經過與不經過中轉點的距離哪個更短。同時，我們需要引入2個矩陣，一個鄰接矩陣D，用來計算每個相鄰點的距離，也就是我們的已知條件，第二個矩陣P，則用來表示中間點k的代數。比如說P中p[i,j]的值就是i與j兩點的中間點代數。
我們在進行Floyd演算法的時候，也要像Dijkstra演算法一樣，不停的更新這兩個矩陣。當我們根據一點規律變化中間點k的時候，也要遍歷所有的最小距離和中間點，若D[i,j]<D[i,k]+D[j,k],則矩陣D中的distance[i,j]需要改變成D[i,k]+D[j,k]，矩陣P中的P[i,j]要改為k。在遍歷掉所有點為中心之後，Floyd演算法完成。
這個中轉點的思想，我們可以想像現實中的自ekd旅行駕游問題，有的城市間的道路好走，比如存在高速公路，其需要的時間就越短，有的城市間只有原始的泥濘小道，行駛時就很耗時間。
比如A地直接到B地需要7小時
A地經由C地再到B地，則要1+4=5小時
A地經由C地再到D地再到B地，則要1+1+1小時。
換言之，這類似動態規則的背包問題，從A地到B地，每個中轉點可以選擇也可以不選擇，這個邏輯就是對應代碼中的鬆弛操作。要求出所有地方（頂點）之間的最短距離，就需要n^3次鬆弛操作（三重循環）
Floyd的核心5行代碼：
for(k=0;k<n;k++)//中轉站0~k
for(i=0;i<n;i++) //i為起點
for(j=0;j<n;j++) //j為終點
if(d[i][j]>d[i][k]+d[k][j])//鬆弛操作
d[i][j]=d[i][k]+d[k][j];
需要注意的是，Floyd演算法都是圍繞頂點展開，因此其表示法只能選擇相鄰距陣。在相鄰距陣中，我們默認所有頂點的權重是無限大，表示它們都不相鄰，其實這在Floyd演算法有點不對，因為頂點到它自身的距離應該為零，因此這個要改動一下。
其完整實現如下：
class GraphByMatrix {
constructor(vertices, isDirected = false) {
var n = vertices.length;
var matrix = [];
//建立一個正方形
for (var i = 0; i < n; i++) {
matrix[i] = []
for (var j = 0; j < n; j++) {
matrix[i][j] = Infinity
}
}
var map = {}
for (var i = 0; i < vertices.length; i++) {
map[vertices[i]] = i
}
this.matrix = matrix; // 矩陣
this.vertices = vertices; // 頂點數組（裡面只能是索引值）
this.map = map
this.isDirected = false;
}
addEdge(a, b, weight) {
var aIndex = this.map[a]
var bIndex = this.map[b]
if(aIndex === void 0 || bIndex === void 0 ){
throw "請提前設置頂點數組"
}
this.matrix[aIndex][bIndex] = weight || 1
if(!this.isDirected){
this.matrix[bIndex][aIndex] = weight || 1
}
}
toString(obj) {
function addWhiteSpace(str, n, left) {
if (str.length < n) {
if (left) {
return addWhiteSpace( + str, n, false)
} else {
return addWhiteSpace(str + , n, true)
}
}
return str
}
obj = obj || this.matrix;
return obj.map(function (row) {
return row.map(function (el) {
return addWhiteSpace(el + "", 8, true)
}).join( )
}).join("
");
}
floyd() {
var n = this.matrix.length, distance = [], path = []
for (var i = 0; i < n; i++) {
distance[i] = []
path[i] = []
for (var j = 0; j < n; j++) {
//重點，自己到自己為零
distance[i][j] = i === j ? 0 : this.matrix[i][j]
path[i][j] = -1;
}
}
for (var k = 0; k < n; k++) {
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
if (distance[i][j] > distance[i][k] + distance[k][j]) {
distance[i][j] = distance[i][k] + distance[k][j]
path[i][j] = k
if (i == j && this.dist[i][j] < 0) {//發現了負權環
return false;
}
}
}
}
}
console.log("鄰接矩陣")
console.log(this + "")
console.log("最短路徑")
console.log(this.toString(distance))
console.log("path矩陣")
console.log(this.toString(path))
this.printPath(distance, path, n)
}
genPath(path, i, j, s) {
var k = path[i][j];
if (k == -1) {
return;
}
this.genPath(path, i, k, s);
s.push(k)
this.genPath(path, k, j, s);
}
printPath(distance, path, n) {
var i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (this.matrix[i][j] === Infinity && i == j) {
continue
}
var s = this.vertices[i] + 到 + this.vertices[j] + " 最短距離為:" + distance[i][j] +
s += path:
var stack = [i]
this.genPath(path, i, j, stack)
stack.push(j)
s += stack.join(->)
console.log(s)
}
}
}
}
var g = new GraphByMatrix([0, 1, 2, 3, 4, 5, 6, 7, 8], true);
g.addEdge(0, 1, 1)
g.addEdge(0, 2, 5)
g.addEdge(1, 2, 3)
g.addEdge(1, 3, 7)
g.addEdge(1, 4, 5)
g.addEdge(2, 4, 1)
g.addEdge(2, 5, 7)
g.addEdge(3, 4, 2)
g.addEdge(3, 6, 3)
g.addEdge(4, 5, 3)
g.addEdge(4, 6, 6)
g.addEdge(4, 7, 9)
g.addEdge(5, 7, 5)
g.addEdge(6, 7, 2)
g.addEdge(6, 8, 7)
g.addEdge(7, 8, 4)
g.floyd()
推薦閱讀：
