图-最短路径-弗洛伊德算法

思路

• 通过中间点修正矩阵

场景

• 所有顶点至所有顶点的最短路径问题

案例

代码

package com.map;

import lombok.Data;

import java.util.Arrays;

/**
 * ShortestPath_FLOYD class
 */
@Data
public class ShortestPath_FLOYD {
    private int[][] P; // 路径下标
    private int[][] D; // 带权长度

    public final static int MAX = Integer.MAX_VALUE / 2;



    public  void FLOYD(int map[][]) {
        int num = map.length;
        P = new int[num][num];
        D = new int[num][num];
        for(int v = 0; v < num; v ++) {
            for(int w = 0; w < num; w ++) {
                D[v][w] = map[v][w];
                P[v][w] = w;
            }
        }
        for(int k = 0; k < num; k ++) {
            for(int v = 0; v < num; v ++) {
                for(int w = 0; w < num; w ++) {
                    if(D[v][w] > D[v][k] + D[k][w]) {
                        D[v][w] = D[v][k] + D[k][w];
                        P[v][w] = P[v][k];
                    }
                }
            }
        }

    }


    public static void main(String[] args) {
        // 模式测试数据
        int[][] data = new int[16][3];
        data[0][0] = 0; data[0][1] = 1; data[0][2] = 1;
        data[1][0] = 0; data[1][1] = 2; data[1][2] = 5;
        data[2][0] = 1; data[2][1] = 2; data[2][2] = 3;
        data[3][0] = 1; data[3][1] = 4; data[3][2] = 5;
        data[4][0] = 1; data[4][1] = 3; data[4][2] = 7;
        data[5][0] = 2; data[5][1] = 5; data[5][2] = 7;
        data[12][0] = 2; data[12][1] = 4; data[12][2] = 1;
        data[6][0] = 3; data[6][1] = 4; data[6][2] = 2;
        data[7][0] = 4; data[7][1] = 5; data[7][2] = 3;
        data[8][0] = 3; data[8][1] = 6; data[8][2] = 3;
        data[9][0] = 4; data[9][1] = 6; data[9][2] = 6;
        data[10][0] = 4; data[10][1] = 7; data[10][2] = 9;
        data[13][0] = 5; data[13][1] = 7; data[13][2] = 5;
        data[11][0] = 6; data[11][1] = 7; data[11][2] = 2;
        data[14][0] = 6; data[14][1] = 8; data[14][2] = 7;
        data[15][0] = 7; data[15][1] = 8; data[15][2] = 4;

        // 初始化邻接矩阵
        int[][] map = new int[9][9];
        int num = map.length;
        for(int i = 0; i < num  ; i ++) {
            for (int j = 0; j <num ; j ++) {
                if(i == j) {
                    map[i][j] = 0;
                } else {
                    map[i][j] = MAX;
                }
            }
        }

        for(int i = 0; i < 16; i ++) {
            map[data[i][0]][data[i][1]] = data[i][2];
            map[data[i][1]][data[i][0]] = data[i][2];

        }
        System.out.println("邻接矩阵：");
        for(int i = 0; i < num; i ++ ) {
            System.out.println(Arrays.toString(map[i]));
        }


        ShortestPath_FLOYD shortestPath_floyd = new ShortestPath_FLOYD();
        shortestPath_floyd.FLOYD(map);

        System.out.println(" 最短路径权值数组：");
        for(int i = 0; i < num; i ++) {
            System.out.println(Arrays.toString(shortestPath_floyd.getD()[i] ));
        }
        System.out.println(" 前驱节点数组：" );
        for(int i = 0; i < num; i ++) {
            System.out.println(Arrays.toString(shortestPath_floyd.getP()[i] ));
        }

    }
}

控制台输出

邻接矩阵：
[0, 1, 5, 1073741823, 1073741823, 1073741823, 1073741823, 1073741823, 1073741823]
[1, 0, 3, 7, 5, 1073741823, 1073741823, 1073741823, 1073741823]
[5, 3, 0, 1073741823, 1, 7, 1073741823, 1073741823, 1073741823]
[1073741823, 7, 1073741823, 0, 2, 1073741823, 3, 1073741823, 1073741823]
[1073741823, 5, 1, 2, 0, 3, 6, 9, 1073741823]
[1073741823, 1073741823, 7, 1073741823, 3, 0, 1073741823, 5, 1073741823]
[1073741823, 1073741823, 1073741823, 3, 6, 1073741823, 0, 2, 7]
[1073741823, 1073741823, 1073741823, 1073741823, 9, 5, 2, 0, 4]
[1073741823, 1073741823, 1073741823, 1073741823, 1073741823, 1073741823, 7, 4, 0]
 最短路径权值数组：
[0, 1, 4, 7, 5, 8, 10, 12, 16]
[1, 0, 3, 6, 4, 7, 9, 11, 15]
[4, 3, 0, 3, 1, 4, 6, 8, 12]
[7, 6, 3, 0, 2, 5, 3, 5, 9]
[5, 4, 1, 2, 0, 3, 5, 7, 11]
[8, 7, 4, 5, 3, 0, 7, 5, 9]
[10, 9, 6, 3, 5, 7, 0, 2, 6]
[12, 11, 8, 5, 7, 5, 2, 0, 4]
[16, 15, 12, 9, 11, 9, 6, 4, 0]
 前驱节点数组：
[0, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 2, 2, 2, 2, 2, 2]
[1, 1, 2, 4, 4, 4, 4, 4, 4]
[4, 4, 4, 3, 4, 4, 6, 6, 6]
[2, 2, 2, 3, 4, 5, 3, 3, 3]
[4, 4, 4, 4, 4, 5, 7, 7, 7]
[3, 3, 3, 3, 3, 7, 6, 7, 7]
[6, 6, 6, 6, 6, 5, 6, 7, 8]
[7, 7, 7, 7, 7, 7, 7, 7, 8]

Process finished with exit code 0

如何通过P 得到具体的最短路径

v0->v8 为例
P[v0][v8] = 1  路径为：v0->v1
P[v1][v8] = 2  路径为：v0-v1->v2
....
v0->v1->v2->v4->v3->v6->v7->v8

时间复杂度

-O(n3)