算法——图论——最短路径——Floyd / 传递闭包

这篇具有很好参考价值的文章主要介绍了算法——图论——最短路径——Floyd / 传递闭包。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

 Floyd-Warshall(弗洛伊德)算法

传递闭包

一、试题 算法训练 盾神与离散老师2 


 

 Floyd-Warshall(弗洛伊德)算法

  • 求所有顶点到所有顶点的最短路径问题
  • 弗洛伊德算法(Floyd-Warshall algorithm)是一种用于寻找图中所有顶点对之间最短路径的动态规划算法。
  • 该算法可以处理带有负权边但不含负权环的加权有向图或无向图。
  • 弗洛伊德算法的核心思想是利用三重循环遍历所有顶点,逐步更新每对顶点之间的最短路径的信息。

弗洛伊德算法的示例代码:

import java.util.Arrays;

public class FloydWarshall {

    public static void main(String[] args) {
        int INF = 99999; // 表示无穷大
        int[][] graph = {
            {0, 5, INF, 10},
            {INF, 0, 3, INF},
            {INF, INF, 0, 1},
            {INF, INF, INF, 0}
        };

        floydWarshall(graph);
    }

    public static void floydWarshall(int[][] graph) {
        int V = graph.length;
        int[][] dist = new int[V][V];

        // 初始化距离矩阵为图的邻接矩阵
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // 迭代更新距离矩阵
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 打印最短路径距离
        printSolution(dist);
    }

    public static void printSolution(int[][] dist) {
        int V = dist.length;
        System.out.println("距离矩阵:");
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][j] == 99999) {
                    System.out.print("INF ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}

传递闭包

  • 给定一个集合,以及若干对元素之间的传递关系,传递闭包问题是求所有元素之间的传递(连通)关系。
  • 例如,包括3个元素的集合{a,b,c},给定传递关系a-->b, b-->c,那么可推导出a-->c
  • 用Floyd算法解决传递闭包问题
  • 可用bitset优化复杂度

传递闭包的示例代码:

    // 使用Floyd算法计算最短路径
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    // 如果经过节点k可以从节点i到达节点j,则更新传递闭包矩阵
                    if (matrix[i][k] == 1 && matrix[k][j] == 1) {
                        matrix[i][j] = 1;
                    }
                }
            }
        }

一、试题 算法训练 盾神与离散老师2 

问题描述
  有一天,盾神觉得自己离散课快要挂了,于是亲自找到离散老师WH,请教如何才能不挂科。WH老师说,只要你做出下面那题,你就可以不挂了!但是盾神不会做T_T只能请教你了。
  有N个人,i和j可能认识,可能不认识。i一定认识i。如果i认识j,j不一定认识i。但是如果i认识j,j认识k,i必定认识k。给出目前掌握的N个人互相的认识关系,求用已知的关系推断出来的N个人互相的人事关系。
输入格式
  输入第一行为一个数N。
  接下来是一个N*N的矩阵,第i行第j个数是1的话表示i认识j,0的话表示i不一定认识j。不会出现除0和1之外的其他数。数与数之间用一个空格隔开。第i行第i列不一定是1。
输出格式
  输出一个N*N的矩阵,第i行第j列的意思如输入。数与数之间用一个空格隔开。第i行第i列必须是1。
样例输入
  3
  0 1 0
  0 0 1
  0 0 0
样例输出
  1 1 1
  0 1 1
  0 0 1
数据规模和约定
  N<=500

分析:

  •  使用Floyd算法解决,套用代码即可
  • 一个三重for循环
package no1_1;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[][] matrix = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            scanner.nextLine();
            for (int j = 1; j <= n; j++) {
                matrix[i][j] = scanner.nextInt();
                if(i == j) {//自己一定认识自己
                    matrix[i][j] = 1;
                }
            }
        }

        // 使用多重循环直接更新矩阵中的间接关系
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (matrix[i][j] == 0 && matrix[i][k] == 1 && matrix[k][j] == 1) {
                        matrix[i][j] = 1;
                    }
                }
            }
        }
        //打印矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

 文章来源地址https://www.toymoban.com/news/detail-830513.html

到了这里,关于算法——图论——最短路径——Floyd / 传递闭包的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)

    目录 问题分类  无权图单源最短路径算法 思路 伪代码 时间复杂度 代码实现(C语言) 有权图单源最短路径算法 Dijkstra(迪杰斯特拉)算法 伪代码  时间复杂度  代码实现(C语言) 多源最短路径算法 两种方法 Floyd算法 代码实现(C语言) 最短路径问题的抽象 在网络中,求

    2024年02月08日
    浏览(58)
  • 数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。

    最短路径的算法有两个, Dijkstra算法 和 Floyd算法 。 Dijkstra算法 解决的是 单源 最短路径问题 。 Floyd算法解决的是 多源 最短路径问题,并且可以处理负权图 。 今天要讲的就是Dijkstra算法。 加: feng--Insist (大写的i),进java交流群讨论互联网+技术。可索要PPT等资料。 其他资料

    2024年02月11日
    浏览(58)
  • 【算法基础:搜索与图论】3.4 求最短路算法(Dijkstra&bellman-ford&spfa&Floyd)

    关于最短路可见:https://oi-wiki.org/graph/shortest-path/ 无向图 是一种 特殊的 有向图。(所以上面的知识地图上没有区分边有向还是无向) 关于存储:稠密图用邻接矩阵,稀疏图用邻接表。 朴素Dijkstra 和 堆优化Dijkstra算法的 选择就在于图 是 稠密的还是稀疏的。 算法步骤: 有一

    2024年02月16日
    浏览(44)
  • Floyd判联通(传递闭包) & poj1049 sorting it all out

    Floyd传递闭包顾名思义就是把判最短路的代码替换成了判是否连通的代码,它可以用来判断图中两点是否连通。板子大概是这个样的: 给定 n个变量和 m个不等式。其中 n小于等于 26,变量分别用前 n的大写英文字母表示。 不等式之间具有传递性,即若 AB 且 BC,则 AC。 请从前

    2024年02月04日
    浏览(36)
  • 图论 - 最短路(Dijkstra、Bellman-Ford、SPFA、Floyd)

    单源:在边权正数时,稠密图用朴素Dijkstra,稀疏图用堆优化Dijkstra;存在负权边时,一般用SPFA,但是如果限制在k步内,则用Bellman-Ford。多源:只有Floyd,这个由于时间复杂度太高,在算法比赛中很少遇见。 1.问题描述 给定一个 n 个点 m 条边的有向图,图中可能存在重边和自

    2024年04月14日
    浏览(37)
  • Acwing.854 Floyd求最短路 (Floyd算法)

    给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。 再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输\\\"impossible”。 数据保证图中不存在负权回路。 第一行包含三个整数n, m, k 接下来m行,每行包含三

    2024年02月13日
    浏览(36)
  • 图算法——求最短路径(Floyd算法)

    目录 一、什么是最短路径 二、弗洛伊德(Floyd)算法 三、测试程序         求图的最短路径在实际生活中有许多应用,比如说在你在一个景区的某个景点,参观完后,要怎么走最少的路程到你想参观的下个景点,这就利用到了求图最短路径的算法。求图的最短路径有很多

    2024年02月07日
    浏览(38)
  • Floyd算法求解最短路径

      Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德。   核心思路:通过一个图的权值矩阵求出它的每

    2024年02月05日
    浏览(33)
  • 【MATLAB】最短路径Floyd算法

    1.1适用范围 ∙ bullet ∙ 求每队顶点的最短路径 ∙ bullet ∙ 有向图、无向图和混合图 1.2算法思想 直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2)…D(n)( 每次加入一个点然后更新最短路径矩阵D ),D(n)是图的最短距离矩阵,同时引入一个后继

    2024年02月16日
    浏览(32)
  • 【数据结构】图—弗洛伊德(Floyd)算法

    上文介绍了迪杰斯特拉(Dijkstra)算法,计算网图的某个源点到其余各个顶点的最短路径问题(边权值为非负值),本文介绍另一个求最短路径的算法——弗洛伊德算法,它是计算所有顶点到所有顶点的最短路径,其时间复杂度为 O ( n 3 ) O(n^3) O ( n 3 ) ,其算法相比Dijkstra算法更加

    2024年02月12日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包