【图】最短路径：弗洛伊德（Floyd）算法

特点

弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理无向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。

基本思想

通过 Floyd 算法计算图 G=(V,{E}) 中各个顶点的最短路径时，需要引入两个矩阵：

• 矩阵 D 中的元素 a[i][j] ，表示顶点 i 到顶点 j 的最短路径权值和。
• 矩阵 P 中的元素 b[i][j]，表示顶点 i 到顶点 j 经过了 b[i][j] 值对应顶点。

假设图 G 中顶点个数为 N，则需要对矩阵 D 和矩阵 P 进行 N 次更新：

1. 初始时，矩阵 D−1 中顶点 a[i][j] 的距离为顶点 i 到顶点 j 的权值（如果 i 和 j 不相邻，则 a[i][j]=∞），矩阵 P−1 的值为顶点 b[i][j] 的 j 的值。
2. 然后，对矩阵 D 进行 N 次更新。
3. 第 k=0 次更新时，D0[i][j]=min{D−1[i][j],D−1[i][0]+D−1[0][j]}，若有更新，则对应P0[i][j]=P0[i][0]。
4. 同理，第 k 次更新时，Dk[i][j]=min{Dk−1[i][j],Dk−1[i][k]+D−1[k][j]}，若有更新，则对应Pk[i][j]=Pk[i][k]。
5. 直到 k 等于 N 结束。

算法实例

给出一个无向图：

1、第一步，先初始化两个矩阵 D−1,P−1：
&&
2、k=0，即所有的顶点都经过 v0 中转，没有任何变化。
&&
3、k=1，即所有的顶点都经过 v1 中转，变化如下。
&&
4、k=2，即所有的顶点都经过 v2 中转，变化如下。
&&
5、k=3，即所有的顶点都经过 v3 中转，变化如下。
&&
6、k=4，即所有的顶点都经过 v4 中转，变化如下。
&&
。。。
7、当k=8时，两矩阵数据如图：
&&

实现

/* 图 邻接矩阵 */
function Graph(v) {
    this.v = v;
    this.e = [];
    //边数组初始化
    for (var i = 0; i < this.v.length; i++) {
        this.e[i] = [];
        for (var j = 0; j < this.v.length; j++) {
            if (i === j) {
                this.e[i][j] = 0;
            } else {
                this.e[i][j] = 65535;
            }
        }
    }

    this.D = [];
    this.P = [];
}

Graph.prototype.addEdge = function (v1, v2, data) {
    this.e[v1][v2] = data;
    this.e[v2][v1] = data;
}

Graph.prototype.shortestPath_Floyd = function () {
    /* 初始化 D 与 P */
    this.D = this.e; /* D为路径的权值 */
    for (i = 0; i < this.v.length; i++) {
        this.P[i] = [];
        for (var j = 0; j < this.v.length; j++) {
            this.P[i][j] = j;
        }
    }

    var i, j, k;
    for (k = 0; k < this.v.length; k++) {
        for (i = 0; i < this.v.length; i++) {
            for (j = 0; j < this.v.length; j++) {
                /* 如果经过下标为 k 顶点路径比原两点间路径更短 */
                if (this.D[i][j] > this.D[i][k] + this.D[k][j]) {
                    /* 将当前两点间权值设为更小的一个 */
                    this.D[i][j] = this.D[i][k] + this.D[k][j];
                    this.P[i][j] = this.P[i][k]; /* 路径设置经过下标为 k 的顶点 */
                }
            }
        }
    }
}

/* 最短路径的显示 */
Graph.prototype.shortestPathShow = function () {
    for(var i =0;i<this.v.length;i++){
        for(var j=0;j<this.v.length;j++){
            console.group("v"+i+" - v"+j+" 的路径长度为"+this.D[i][j]+"，路径为:");
            console.log(i); /* 打印源点 */
            var k = this.P[i][j]; /* 获得第一个路径顶点下标 */
            while(k!=j){
                console.log(k); /* 打印路径顶点 */
                k=this.P[k][j];
            }
            console.log(j); /* 打印终点 */
            console.groupEnd();
        }
    }
}

/* 测试代码 */
var v= [0,1,2,3,4,5,6,7,8];
var g = new Graph(v);
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.shortestPath_Floyd();
console.log(g);
g.shortestPathShow();

控制台打印的信息：