1, What is Freudian algorithm?

Floyd algorithm, also known as interpolation method, is an algorithm that uses the idea of dynamic programming to find the shortest path between multiple source points in a given weighted graph. It is similar to Dijkstra algorithm. The difference is that Dijkstra algorithm can only calculate the shortest path from one endpoint to other endpoints at one time, while Floyd algorithm can calculate the shortest path from all endpoints to other endpoints, Although their time complexity is the third power of n, Floyd algorithm is very concise and elegant.

2, Principle

For any two end points i and j, if there is an intermediate endpoint K and the sum of the weights of i - > k and K - > J is less than i - > J, i - > k - > J is used to replace the path of i - > J, otherwise it remains unchanged, where i - > k can be a logical edge or a practical edge.
How to understand the logical side?
That is, i and K have no direct edges, so the weight of i - > k is theoretically infinite. There is an endpoint a in the middle of i - > k, that is, a, i and K have edges. If the sum of the weights of i - > A and a - > k is finite, it must be less than infinity. Therefore, i - > k can be replaced by i - > a - > K. therefore, the actual path of i - > J is i - > A - > k - > J. Seeing this, i think everyone should understand that Freudian algorithm is to use the middle endpoint to constantly find the shortest path between the two endpoints.

3, Implementation steps

1. Initialization diagram
2. Initialize the weight table and the shortest path table, in which the default direct connection is in the shortest path table; The weight table does not exist. The default value of the table is infinity
3. Take each endpoint as the intermediate endpoint, and cycle through to update the shortest path and weight of the two endpoints
4. Traverse and print the shortest path from all endpoints to other endpoints

4, Implementation code

The code is as follows (example):

public class Test {

    /**
     * Endpoint matrix
     */
    private static final int[][] GRAPH;

    /**
     * Path table
     * SHORT_PATH_TABLE[i][j] == j Indicates I - > J direct, without intermediate node conversion
     */
    private static final int[][] SHORT_PATH_TABLE;

    /**
     * Weight table
     */
    private static final int[][] WEIGHT_TABLE;

    /**
     * Judge whether two nodes have edges
     */
    private static final int NOT_DIRECT_FLAG = -1;


    static {
        GRAPH = new int[9][9];
        SHORT_PATH_TABLE = new int[9][9];
        WEIGHT_TABLE = new int[9][9];
        initGraph();
        initShortPathAndWeight();

    }

    /**
     * Initialize path and weight
     */
    public static void initShortPathAndWeight() {

        for (int i = 0; i < GRAPH.length; i++) {
            for (int j = 0; j < GRAPH.length; j++) {
                WEIGHT_TABLE[i][j] = GRAPH[i][j];
                // By default, all I - > J paths are direct
                SHORT_PATH_TABLE[i][j] = j;
            }
        }
    }

    /**
     * Initialize chart
     */
    public static void initGraph() {
        for (int i = 0; i < GRAPH.length; i++) {
            for (int j = 0; j < GRAPH[i].length; j++) {
                if (i == j) {
                    GRAPH[i][j] = 0;
                } else {
                    GRAPH[i][j] = Integer.MAX_VALUE;
                }

            }
        }
        GRAPH[0][1] = 1;
        GRAPH[1][0] = 1;

        GRAPH[0][2] = 5;
        GRAPH[2][0] = 5;

        GRAPH[1][2] = 3;
        GRAPH[2][1] = 3;

        GRAPH[1][3] = 7;
        GRAPH[3][1] = 7;

        GRAPH[1][4] = 5;
        GRAPH[4][1] = 5;

        GRAPH[2][4] = 1;
        GRAPH[4][2] = 1;

        GRAPH[2][5] = 7;
        GRAPH[5][2] = 7;

        GRAPH[4][3] = 2;
        GRAPH[3][4] = 2;

        GRAPH[6][3] = 3;
        GRAPH[3][6] = 3;

        GRAPH[4][6] = 6;
        GRAPH[6][4] = 6;

        GRAPH[4][7] = 9;
        GRAPH[7][4] = 9;

        GRAPH[4][5] = 3;
        GRAPH[5][4] = 3;

        GRAPH[5][7] = 5;
        GRAPH[7][5] = 5;

        GRAPH[6][7] = 2;
        GRAPH[7][6] = 2;

        GRAPH[6][8] = 7;
        GRAPH[8][6] = 7;

        GRAPH[7][8] = 4;
        GRAPH[8][7] = 4;
    }

    public static void main(String[] args) {
        calculateShortPathAndWeight();
        getShortPathAndWeight();
    }

    /**
     * Calculate the shortest path and weight
     * Core code
     * The third power of time complexity n
     */
    private static void calculateShortPathAndWeight() {

        for (int k = 0; k < GRAPH.length; k++) {
            for (int i = 0; i < GRAPH.length; i++) {
                for (int j = 0; j < GRAPH.length; j++) {
                    if (WEIGHT_TABLE[i][j] > (long) WEIGHT_TABLE[i][k] + (long) WEIGHT_TABLE[k][j]) {
                        WEIGHT_TABLE[i][j] = WEIGHT_TABLE[i][k] + WEIGHT_TABLE[k][j];
                        SHORT_PATH_TABLE[i][j] = SHORT_PATH_TABLE[i][k];
                    }
                }
            }
        }

    }

    /**
     * Traverses the shortest path from all vertices to other vertices
     */
    private static void getShortPathAndWeight() {
        System.out.print("The minimum weight and shortest path from each vertex to other vertices are as follows:");
        for (int i = 0; i < GRAPH.length; i++) {
            for (int j = 0; j < GRAPH.length; j++) {
                System.out.print(String.format("v%s-v%s weight: %s ;", i, j, WEIGHT_TABLE[i][j]));
                int index = SHORT_PATH_TABLE[i][j];
                System.out.print(String.format("path: %s", i));
                while (index != j) {
                    System.out.print(String.format(" -> %s", index));
                    index = SHORT_PATH_TABLE[index][j];
                }
                System.out.print(String.format(" -> %s \n", j));
            }
        }
    }

}

summary

Look at the principle first and then the code. If you understand the principle, you can understand the Freud algorithm

Note: long love is the best company, even if you leave