【程序員必會十大算法】之弗洛伊德算法

JellyBool 發布于2021-09-30 09:47 / 1207人閱讀

摘要：學習資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設置為，否則兩個相加會溢出導致出現負權創建頂點和邊

學習資料

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

代碼

public class Main {    //不能設置為Integer.MAX_VALUE，否則兩個Integer.MAX_VALUE相加會溢出導致出現負權    public static int MaxValue = 10000;    public static int[][] path;    public static void main(String[] args) {        //創建頂點和邊        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}};        //初始化路徑數組        path = new int[matrix.length][matrix.length];        floyd(matrix);    }    //非遞歸實現    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];                        //記錄經由哪個點到達                        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 + "不可達");                    } else {                        System.out.print(i + "到" + j + "的最短路徑長度是：" + 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);    }}

結果

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

云服務器 GPU云服務器 webrtc之vad算法十大機器學習算法機器學習十大算法看動畫學算法之:hashtable

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/121661.html

【程序員必會十大算法】之分治算法（漢諾塔問題）

摘要：應用分治法是一種很重要的算法。字面上的解釋是分而治之，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 ...

codecraft 2021-09-24 09:48 評論0 收藏0
【程序員必會十大算法】之Prim算法

摘要：問題勝利鄉有個村莊現在需要修路把個村莊連通各個村莊的距離用邊線表示權比如距離公里問如何修路保證各個村莊都能連通并且總的修建公路總里程最短代碼重點理解中的三層循環問...

番茄西紅柿 2021-09-28 09:36 評論0 收藏2637
【程序員必會十大算法】之二分查找算法

摘要：遞歸實現不考慮相同數二分查找，不考慮有相同數的情況遞歸找到了考慮有相同數二分查找考慮有相同元素的情況遞歸要查找的值 1.遞歸實現 ①不考慮相同數 /** * 二分查...

YFan 2021-09-24 09:48 評論0 收藏0
【程序員必會十大算法】之貪心算法

摘要：例題假設存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區。例題假設存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區。如何選擇最少的廣播臺，讓...

macg0406 2021-09-27 13:36 評論0 收藏0
【程序員必會十大算法】之騎士周游問題

摘要：騎士周游問題又叫馬踏棋盤問題未優化前沒有策略定義棋盤的行數和列數定義棋盤上的某個點是否被訪問過記錄是否周游結束從第一行第一列開始走，第一次走算第一步，即展示下是棋盤， ...

Baoyuan 2021-09-30 09:47 評論0 收藏0