floyed 算法

floyed 算法/**floyed是用动态规划解决完全最短路的算法,一次调用即可得到任意两个点间的最短路径复杂度为O(n^3),适用于稠密图,顶点数一般在100以内适用结构简单,易于编写floyed算法还可解决传递闭包,判断图是否为连通图在解题时候一般不会只考floyed而是利用floyed得到的结果,进行下一步解题就像二分算法一样,提一

大家好,又见面了,我是你们的朋友全栈君。

/**
    floyed 是用动态规划解决完全最短路的算法,一次调用即可得到任意两个点间的最短路径
    复杂度为O(n^3),适用于稠密图,顶点数一般在100 以内适用

    结构简单,易于编写

    floyed算法还可解决传递闭包,判断图是否为连通图

    在解题时候一般不会只考 floyed 而是利用floyed 得到的结果,进行下一步解题
    就像二分算法一样,提一下竞赛必考二分枚举
*/

const int inf = 0x3f3f3f3f;
const int M = 100;

int map[M][M]; //初始化map[][] = inf;

void addEdge(int u, int v, int w) {
    map[u][v] = w;
    map[v][u] = w; //floyed 也可以解决有向图
}

void floyed(int nv) {
    int i, j, k;
    for (i=1; i<=nv; i++)
        for (j=1; j<=nv; j++)
            for (k=1; k<=nv; k++)
                map[i][j] = min(map[i][j], map[i][k]+map[k][j]);

}

/**
    注意:连接矩阵添边都应该注意是否有重边,floyed 算法既可以解决有向图又可以解决
    无向图,但是不能解决带负权回路的图
*/

收藏于 2011-11-18
来自于百度空间

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/149044.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Netty框架学习之(一):Netty框架简介

    Netty框架学习之(一):Netty框架简介1.简介官方定义为:”Netty是一款异步的事件驱动的网络应用程序框架,支持快速地开发可维护的高性能的面向协议的服务器和客户端”,按照惯例贴上一张HighLevel的架构图:纵观Java系的多种服务器/大数据框架,都离不开Netty做出的贡献,本文对Netty做一个简单的概述2.主要特性Netty有很多重要的特性,主要特性如下:-优雅的设计-统一…

    2022年10月27日
  • 阿里Java高级工程师面试题(含答案)

    阿里Java高级工程师面试题(含答案)1,java堆,分新生代老年代,新生代有Eden,fromsurviver,tosurviver三个空间,堆被所有线程共。eden内存不足时,发生一次minorGC,会把fromsurvivor和eden的对象复制到tosurvivor,这次的to&amp;amp;amp;nbsp;survivor就变成了下次的fromsurvivor,经过多次minorGC,默认15次,达到次数的对象会从survivor…

  • python进阶(15)多线程与多进程效率测试「建议收藏」

    python进阶(15)多线程与多进程效率测试「建议收藏」前言在Python中,计算密集型任务适用于多进程,IO密集型任务适用于多线程正常来讲,多线程要比多进程效率更高,因为进程间的切换需要的资源和开销更大,而线程相对更小,但是我们使用的Python大多

  • Spring源码下载地址

    Spring源码下载地址https://github.com/spring-projects/spring-framework

  • python偏函数理解_python进阶书籍的推荐

    python偏函数理解_python进阶书籍的推荐什么是偏函数partialpython中提供一种对于函数固定属性的函数偏函数的作用把一个函数的某些参数给固定住(也就是设置默认值),返回一个新的函数偏函数的语法使用偏函数必须先导入from

  • mybatis log激活码【永久激活】

    (mybatis log激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/ide…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号