最短路径的求法

最短路径的求法

Floyd算法

初始化代码：

private void init() {
    n = 5;
    a = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a[i][j] = Integer.MAX_VALUE >> 1;
        }
        a[i][i] = 0;
    }
    a[0][1] = 10;
    a[1][0] = 10;
    a[0][3] = 30;
    a[3][0] = 30;
    a[0][4] = 100;
    a[4][0] = 100;
    a[1][2] = 50;
    a[2][1] = 50;
    a[2][3] = 20;
    a[3][2] = 20;
    a[2][4] = 10;
    a[4][2] = 10;
    a[3][4] = 60;
    a[4][3] = 60;
}

Floyd算法：

public void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = Math.min(a[i][j], a[i][k] + a[k][j]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            System.out.println(i + " " + j + ":" + a[i][j]);
        }
    }
}

其实这个算法很好理解（如果理解了的话），首先我们创建一个邻接矩阵，这个时候我们就知道了初始状态下x[i][j]之间的长度，我们在进行遍历节点的时候，A[i][j]标识的就是从i到j节点的最短路径，这个时候还是初始化的值，然后我们可以让节点从i到j的时候再通过K这个节点，这个时候最短路径就变成了从i->k的长度加上k->j的长度之后和已经求得的最短路径得最小值，重复这个过程直到经过所有得K节点，这个时候求得得路径就是最短路径。

迪杰斯特拉最短路径算法（Dijkstra’s）

dijkstra算法基于贪心，贪心算法中最重要的一部分就是贪心策略，贪心算法对不对，就是贪心策略的正确不正确，在这个算法中，贪心策略就是，去寻找点i，满足min(d[i]) i∈B，满足这个条件的点i，必定是无法被继续松弛的点，如果说要松弛点i，那么必定通过A中或者B中的点进行更新，若通过B中的点j进行更新那么松弛之后的路径为d[j] + a[j][i] 由于d[i]已经是最小了，因此d[j]+a[j][i]>d[i] 因此不可能是通过B中的点进行松弛，若通过A中的点m进行松弛，由于m是点集A中的点，因此点m一定松弛过点i，重复的松弛没有意义的。因此，我们找到的点i，现在的d[i]，一定是从源点到点i路径最小的点了，因此，该算法的正确性是可以保证的。

public void dijkstra(int p) {
    int[] d = new int[n];
    Set<Integer> set = new HashSet<>(n);
    set.add(p);
    for (int i = 0; i < n; i++) {
        d[i] = a[p][i];
    }
    while (set.size() < n) {
        //找到点周围最近的一个点
        int le = Integer.MAX_VALUE;
        int num = 0;
        for (int i = 0; i < n; i++) {
            if (!set.contains(i) && le > d[i]) {
                le = d[i];
                num = i;
            }
        }
        //计算将这个点加入集合后最短距离的变化
        for (int i = 0; i < n; i++) {
            if (!set.contains(i)) {
                d[i] = Math.min(d[i], d[num] + a[num][i]);
            }
        }
        set.add(num);
    }
    for (int i = 0; i < n; i++) {
        System.out.println("点" + p + "到点" + i + "的距离为：" + d[i]);
    }
}