目录

Floyd(弗洛伊德)算法

求所有顶点的最短路径? 方法一:每次以一个顶点为源点,重复执行Dijkstra算法n次 方法二:(Floyd)弗洛伊德算法

Floyd算法思想

  • 逐个顶点试探
  • 从vi到vj的所有可能存在的路径中,因为某个顶点的加入,重新选出一条长度最短的路径。

算法步骤

https://gitee.com/lienhui68/picStore/raw/master/null/20200705194842.png

  1. 初始时设置一个n阶方阵,令其对角线元素为0,若存在弧(vi,vj),则对应元素为权值,否则无穷大。 各顶点之间的距离是直达的。 https://gitee.com/lienhui68/picStore/raw/master/null/20200705195140.png
  2. 逐步试着在原直接路径中增加中间顶点,若加入中间顶点后路径变短,则修改之;否则,维持原值。所有顶点试探完毕,算法结束。 https://gitee.com/lienhui68/picStore/raw/master/null/20200705195650.png

代码实现 matrix[i][j]表示从i到j的距离, 只有通过第3个位置,i和j之间的距离才有可能变短,我们设第3个位置为k 当k=1, matrix[i][j]的最短距离应该是Math.min(matrix[i][j], matrix[i][1] + matrix[1][j]), 注意是有向图,顺序很关键。 当k=2时, 可以通过两个点进行中转,k=1已经产生了结果,接下来只要看k=2是否会缩短距离即可,这是递推的过程, 我们可以运用动态规划自顶向下来分析。 先定义状态$f_k(i,j)$表示引入k个顶点,从i到j的最短路径,那么$f_{k-1}(i,j)$表示在不中转k的情况下i到j的最短路径,两种情况要么中转要么没中转,所以取最小值,状态转换方程如下: $f_k(i,j)=min(f_{k-1}(i,j), f_k(i,j))$,$f_{k-1}(i,j)$就是$f(i,j)$,$f_k(i,j)=f[i][k] + f[k][j]$ 核心代码就几行,主要是对递推公式的实现

1
2
3
4
5
6
7
8
9
    public void floyd() {
        for (int k = 0; k < vertexNames.size(); k++) {
            for (int i = 0; i < vertexNames.size(); i++) {
                for (int j = 0; j < vertexNames.size(); j++) {
                    matrix[i][j] = Math.min(matrix[i][k] + matrix[k][j], matrix[i][j]);
                }
            }
        }
    }

完整代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
package com.eh.ftd.dsa.ds;

import com.google.common.collect.Lists;

import java.util.Arrays;
import java.util.List;

/**
 * 弗洛伊德算法
 *
 * @author David Li
 * @create 2020/07/06 01:29
 */
public class Floyd {
    private final static int INF = 999999;


    /**
     * 图的邻接矩阵表现形式
     * 0表示自己指向自己,值为Integer.MAX_VALUE表示无穷远
     */
    private int[][] matrix;

    /**
     * 顶点的表现形式
     */
    private List<String> vertexNames;

    public Floyd(List<String> vertexNames) {
        this.matrix = new int[vertexNames.size()][vertexNames.size()];
        this.vertexNames = vertexNames;
        for (int i = 0; i < vertexNames.size(); i++) {
            for (int j = 0; j < vertexNames.size(); j++) {
                if (i != j) {
                    matrix[i][j] = 999999;
                }
            }
        }
    }

    /**
     * 获得顶点对应下标
     *
     * @param vertexName
     * @return
     */
    private int getIndexByVertexName(String vertexName) {
        for (int i = 0; i < vertexNames.size(); i++) {
            if (vertexName.equals(vertexNames.get(i))) {
                return i;
            }
        }
        throw new RuntimeException();
    }

    public void floyd() {
        for (int k = 0; k < vertexNames.size(); k++) {
            for (int i = 0; i < vertexNames.size(); i++) {
                for (int j = 0; j < vertexNames.size(); j++) {
                    matrix[i][j] = Math.min(matrix[i][k] + matrix[k][j], matrix[i][j]);
                }
            }
        }
    }


    public void printMatrix() {
        for (int[] arr : matrix) {
            System.out.println(Arrays.toString(arr));
        }
    }

    /**
     * 有向图
     *
     * @param v1
     * @param v2
     * @param weight
     */
    public void buildEdge(String v1, String v2, int weight) {
        int idx1 = getIndexByVertexName(v1);
        int idx2 = getIndexByVertexName(v2);
        matrix[idx1][idx2] = weight;
    }

    public static void main(String[] args) {
        List cites = Lists.newArrayList("v0", "v1", "v2", "v3", "v4", "v5", "v6");
        Floyd floyd = new Floyd(cites);
        floyd.buildEdge("v0", "v1", 13);
        floyd.buildEdge("v0", "v2", 8);
        floyd.buildEdge("v0", "v4", 30);
        floyd.buildEdge("v0", "v6", 32);

        floyd.buildEdge("v1", "v5", 9);
        floyd.buildEdge("v1", "v6", 7);

        floyd.buildEdge("v2", "v3", 5);
        floyd.buildEdge("v3", "v4", 6);
        floyd.buildEdge("v4", "v5", 2);
        floyd.buildEdge("v5", "v6", 17);
        floyd.floyd();
        floyd.printMatrix();
    }
}