學(xué)習(xí)資料

迪杰斯特拉計(jì)算的是單源最短路徑，而弗洛伊德計(jì)算的是多源最短路徑

代碼

public class Main {    //不能設(shè)置為Integer.MAX_VALUE，否則兩個(gè)Integer.MAX_VALUE相加會(huì)溢出導(dǎo)致出現(xiàn)負(fù)權(quán)    public static int MaxValue = 10000;    public static int[][] path;    public static void main(String[] args) {        //創(chuàng)建頂點(diǎn)和邊        char[] data = {"A","B","C","D","E","F","G"};        int[][] matrix = {                {10000,5,7,10000,10000,10000,2},                {5,10000,10000,9,10000, 10000,3},                {7,10000,10000,10000,8,10000,10000},                {10000,9,10000,10000,10000,4,10000},                {10000,10000,8,10006,10000,5,4},                {10000,10000,10000,4,5,10000,6},                {2,3,10000,10000,4,6,10000}};        //初始化路徑數(shù)組        path = new int[matrix.length][matrix.length];        floyd(matrix);    }    //非遞歸實(shí)現(xiàn)    public static void floyd(int[][] matrix) {        for (int i = 0; i < matrix.length; i++) {            for (int j = 0; j < matrix.length; j++) {                path[i][j] = -1;            }        }        for (int m = 0; m < matrix.length; m++) {            for (int i = 0; i < matrix.length; i++) {                for (int j = 0; j < matrix.length; j++) {                    if (matrix[i][m] + matrix[m][j] < matrix[i][j]) {                        matrix[i][j] = matrix[i][m] + matrix[m][j];                        //記錄經(jīng)由哪個(gè)點(diǎn)到達(dá)                        path[i][j] = m;                    }                }            }        }        for (int i = 0; i < matrix.length; i++) {            for (int j = 0; j < matrix.length; j++) {                if (i != j) {                    if (matrix[i][j] == MaxValue) {                        System.out.println(i + "到" + j + "不可達(dá)");                    } else {                        System.out.print(i + "到" + j + "的最短路徑長(zhǎng)度是：" + matrix[i][j]);                        System.out.print("最短路徑為：" + i + "->");                        findPath(i, j);                        System.out.println(j);                    }                }            }        }    }    //遞歸尋找路徑    public static void findPath(int i, int j) {        int m = path[i][j];        if (m == -1) {            return;        }        findPath(i, m);        System.out.print(m + "->");        findPath(m, j);    }}

結(jié)果

0到1的最短路徑長(zhǎng)度是：5最短路徑為：0->10到2的最短路徑長(zhǎng)度是：7最短路徑為：0->20到3的最短路徑長(zhǎng)度是：12最短路徑為：0->6->5->30到4的最短路徑長(zhǎng)度是：6最短路徑為：0->6->40到5的最短路徑長(zhǎng)度是：8最短路徑為：0->6->50到6的最短路徑長(zhǎng)度是：2最短路徑為：0->61到0的最短路徑長(zhǎng)度是：5最短路徑為：1->01到2的最短路徑長(zhǎng)度是：12最短路徑為：1->0->21到3的最短路徑長(zhǎng)度是：9最短路徑為：1->31到4的最短路徑長(zhǎng)度是：7最短路徑為：1->6->41到5的最短路徑長(zhǎng)度是：9最短路徑為：1->6->51到6的最短路徑長(zhǎng)度是：3最短路徑為：1->62到0的最短路徑長(zhǎng)度是：7最短路徑為：2->02到1的最短路徑長(zhǎng)度是：12最短路徑為：2->0->12到3的最短路徑長(zhǎng)度是：17最短路徑為：2->4->5->32到4的最短路徑長(zhǎng)度是：8最短路徑為：2->42到5的最短路徑長(zhǎng)度是：13最短路徑為：2->4->52到6的最短路徑長(zhǎng)度是：9最短路徑為：2->0->63到0的最短路徑長(zhǎng)度是：12最短路徑為：3->5->6->03到1的最短路徑長(zhǎng)度是：9最短路徑為：3->13到2的最短路徑長(zhǎng)度是：17最短路徑為：3->5->4->23到4的最短路徑長(zhǎng)度是：9最短路徑為：3->5->43到5的最短路徑長(zhǎng)度是：4最短路徑為：3->53到6的最短路徑長(zhǎng)度是：10最短路徑為：3->5->64到0的最短路徑長(zhǎng)度是：6最短路徑為：4->6->04到1的最短路徑長(zhǎng)度是：7最短路徑為：4->6->14到2的最短路徑長(zhǎng)度是：8最短路徑為：4->24到3的最短路徑長(zhǎng)度是：9最短路徑為：4->5->34到5的最短路徑長(zhǎng)度是：5最短路徑為：4->54到6的最短路徑長(zhǎng)度是：4最短路徑為：4->65到0的最短路徑長(zhǎng)度是：8最短路徑為：5->6->05到1的最短路徑長(zhǎng)度是：9最短路徑為：5->6->15到2的最短路徑長(zhǎng)度是：13最短路徑為：5->4->25到3的最短路徑長(zhǎng)度是：4最短路徑為：5->35到4的最短路徑長(zhǎng)度是：5最短路徑為：5->45到6的最短路徑長(zhǎng)度是：6最短路徑為：5->66到0的最短路徑長(zhǎng)度是：2最短路徑為：6->06到1的最短路徑長(zhǎng)度是：3最短路徑為：6->16到2的最短路徑長(zhǎng)度是：9最短路徑為：6->0->26到3的最短路徑長(zhǎng)度是：10最短路徑為：6->5->36到4的最短路徑長(zhǎng)度是：4最短路徑為：6->46到5的最短路徑長(zhǎng)度是：6最短路徑為：6->5