核心思想

結(jié)合動(dòng)態(tài)規(guī)劃思想，通過(guò)不斷迭代中轉(zhuǎn)點(diǎn)k后兩點(diǎn)i、j之間的最短路徑來(lái)求解。

代碼及注釋

package others;
/**
 * 只有五行的最短路徑求解算法 ——FloydWarshall
 * @author XZP
 * 0表示自身
 * INF表示圖中兩點(diǎn)不可達(dá)
 * 大于零的數(shù)字表示兩點(diǎn)直接的直接距離
 *
 */
public class FloydWarshall {
//  public static int INF = Integer.MAX_VALUE; // 表示圖中兩頂點(diǎn)不可達(dá)
    public static int INF = 99999; // 注意后面兩個(gè)INF相加可能溢出的情況，這些都是需要注意的細(xì)節(jié)
    public static int[][] graph = {
            {0, 2, 6, 4 },
            {INF, 0, 3, INF},
            {7, INF, 0, 1},
            {5, INF, 12, 0}
    };
    public static int size = graph.length;
    public static void main(String[] args) {
        floyd(graph);
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }
    /**
     * 該算法的核心代碼，只有五行！
     * 時(shí)間復(fù)雜度：O(N^3)
     * @param matrix
     */
    public static void floyd(int[][] matrix) {
        for (int k = 0; k < size; k++) {
            for (int i = 0; i < size; i++) {
                for (int j =0; j <size; j++) {
                    // 動(dòng)態(tài)規(guī)劃的思想，k表示經(jīng)過(guò)k點(diǎn)中轉(zhuǎn)，如果經(jīng)過(guò)k中轉(zhuǎn)距離更好則替換之
                    if (matrix[i][j] > matrix[i][k] + matrix[k][j]) {
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
                    }
                }
            }
        }
    }
}