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)


相关推荐

  • VC的调试中,AssertValid和Dump函数的应用(转载)

    VC的调试中,AssertValid和Dump函数的应用(转载)VC的调试中,AssertValid和Dump函数的应用??楼主mei2004mei2004(aaa)2005-12-0209:47:24在VC/MFC/基础类提问rt.  在debug调试中,AssertValid和Dump 这两个函数怎么进行工作的?    或者说怎么合理利用这两个函数?    …问题点数:100、回复次数:3Top 1楼

  • 动态规划之背包问题(C语言)

    动态规划之背包问题(C语言)动态规划动态规划(英语:Dynamicprogramming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题动态规划思想大致上为:若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。由于通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算

  • python正则匹配数字或者汉字

    python正则匹配数字或者汉字1、正则匹配汉字importrestr1=’hjggj小vjjk明’pat=re.compile(r'[\u4e00-\u9fa5]+’)result=pat.findall(str1)print(result)#输出[‘小’,’明’]2、正则匹配数字importrere.findall(r’\d+’,’hello42I’ma32string30…

  • 【OpenCV入门教程之一】 安装OpenCV:OpenCV 3.0、OpenCV 2.4.8、OpenCV 2.4.9 +VS 开发环境配置

    【OpenCV入门教程之一】 安装OpenCV:OpenCV 3.0、OpenCV 2.4.8、OpenCV 2.4.9 +VS 开发环境配置本系列文章由zhmxy555(毛星云)编写,转载请注明出处。   文章链接: http://blog.csdn.net/poem_qianmo/article/details/19809337 作者:毛星云(浅墨)    邮箱: happylifemxy@163.com  写作当前博文时配套使用OpenCV版本:2.4.8因为读研期间的研究方向是图像处理,所以浅墨这段时间闭门研究了很多OpenCV

  • mysql数据库面试题目及答案_java面试数据库常见问题

    mysql数据库面试题目及答案_java面试数据库常见问题本文的面试题如下:MyisAM和innodb的有关索引的疑问innodb为什么要用自增id作为主键MySql索引是如何实现的说说分库与分表设计(面试过)聚集索引与非聚集索引的区别事务四大特性(ACID)原子性、一致性、隔离性、持久性?事务的并发?事务隔离级别,每个级别会引发什么问题,MySQL默认是哪个级别?MySQL常见的存储引擎InnoDB、MyISAM的区别?【~】数据库三…

  • gdi+ 高速绘制透明窗体

    gdi+ 高速绘制透明窗体

发表回复

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

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