【程序员必会十大算法】之弗洛伊德算法

JellyBool 发布于2021-09-30 09:47 / 927人阅读

摘要：学习资料迪杰斯特拉计算的是单源最短路径，而弗洛伊德计算的是多源最短路径代码不能设置为，否则两个相加会溢出导致出现负权创建顶点和边

学习资料

迪杰斯特拉计算的是单源最短路径，而弗洛伊德计算的是多源最短路径

代码

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

idc机房托管专线服务 webrtc之vad算法十大机器学习算法机器学习十大算法看动画学算法之:hashtable

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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