特点

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

基本思想

通过 Floyd 算法计算图 G=(V,{E})<script type="math/tex" id="MathJax-Element-1">G=(V,\{E\})</script> 中各个顶点的最短路径时，需要引入两个矩阵：

• 矩阵 D<script type="math/tex" id="MathJax-Element-2">D</script> 中的元素 a[i][j]<script type="math/tex" id="MathJax-Element-3">a[i][j]</script> ，表示顶点 i<script type="math/tex" id="MathJax-Element-4">i</script> 到顶点 j<script type="math/tex" id="MathJax-Element-5">j</script> 的最短路径权值和。
• 矩阵 P<script type="math/tex" id="MathJax-Element-6">P</script> 中的元素 b[i][j]<script type="math/tex" id="MathJax-Element-7">b[i][j]</script>，表示顶点 i<script type="math/tex" id="MathJax-Element-8">i</script> 到顶点 j<script type="math/tex" id="MathJax-Element-9">j</script> 经过了 b[i][j]<script type="math/tex" id="MathJax-Element-10">b[i][j]</script> 值对应顶点。

假设图 G<script type="math/tex" id="MathJax-Element-11">G</script> 中顶点个数为 N<script type="math/tex" id="MathJax-Element-12">N</script>，则需要对矩阵 D<script type="math/tex" id="MathJax-Element-13">D</script> 和矩阵 P<script type="math/tex" id="MathJax-Element-14">P</script> 进行 N<script type="math/tex" id="MathJax-Element-15">N</script> 次更新：

1. 初始时，矩阵 D−1<script type="math/tex" id="MathJax-Element-16">D^{-1}</script> 中顶点 a[i][j]<script type="math/tex" id="MathJax-Element-17">a[i][j]</script> 的距离为顶点 i<script type="math/tex" id="MathJax-Element-18">i</script> 到顶点 j<script type="math/tex" id="MathJax-Element-19">j</script> 的权值（如果 i<script type="math/tex" id="MathJax-Element-20">i</script> 和 j<script type="math/tex" id="MathJax-Element-21">j</script> 不相邻，则 a[i][j]=∞<script type="math/tex" id="MathJax-Element-22">a[i][j]=∞</script>），矩阵 P−1<script type="math/tex" id="MathJax-Element-23">P^{-1}</script> 的值为顶点 b[i][j]<script type="math/tex" id="MathJax-Element-24">b[i][j]</script> 的 j<script type="math/tex" id="MathJax-Element-25">j</script> 的值。
2. 然后，对矩阵 D<script type="math/tex" id="MathJax-Element-26">D</script> 进行 N<script type="math/tex" id="MathJax-Element-27">N</script> 次更新。
3. 第 k=0<script type="math/tex" id="MathJax-Element-28">k=0</script> 次更新时，D0[i][j]=min{D−1[i][j],D−1[i][0]+D−1[0][j]}<script type="math/tex" id="MathJax-Element-29">D^0[i][j]=min\{D^{-1}[i][j],D^{-1}[i][0]+D^{-1}[0][j]\}</script>，若有更新，则对应P0[i][j]=P0[i][0]<script type="math/tex" id="MathJax-Element-30">P^0[i][j]=P^0[i][0]</script>。
   • 同理，第 k<script type="math/tex" id="MathJax-Element-31">k</script> 次更新时，Dk[i][j]=min{Dk−1[i][j],Dk−1[i][k]+D−1[k][j]}<script type="math/tex" id="MathJax-Element-32">D^k[i][j]=min\{D^{k-1}[i][j],D^{k-1}[i][k]+D^{-1}[k][j]\}</script>，若有更新，则对应Pk[i][j]=Pk[i][k]<script type="math/tex" id="MathJax-Element-33">P^k[i][j]=P^k[i][k]</script>。
   • 直到 k<script type="math/tex" id="MathJax-Element-34">k</script> 等于 N<script type="math/tex" id="MathJax-Element-35">N</script> 结束。

   • 算法实例

     给出一个无向图：
     
     1、第一步，先初始化两个矩阵 D−1,P−1<script type="math/tex" id="MathJax-Element-36">D^{-1},P^{-1}</script>：
     &&
     2、k=0，即所有的顶点都经过 v0<script type="math/tex" id="MathJax-Element-37">v_0</script> 中转，没有任何变化。
     &&
     3、k=1，即所有的顶点都经过 v1<script type="math/tex" id="MathJax-Element-38">v_1</script> 中转，变化如下。
     &&
     4、k=2，即所有的顶点都经过 v2<script type="math/tex" id="MathJax-Element-39">v_2</script> 中转，变化如下。
     &&
     5、k=3，即所有的顶点都经过 v3<script type="math/tex" id="MathJax-Element-40">v_3</script> 中转，变化如下。
     &&
     6、k=4，即所有的顶点都经过 v4<script type="math/tex" id="MathJax-Element-41">v_4</script> 中转，变化如下。
     &&
     。。。
     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();

     控制台打印的信息：