文档章节

floyd算法c++

侯禹
 侯禹
发布于 2013/09/25 20:03
字数 246
阅读 80
收藏 0
#include <iostream>
#include <cstdio>
#define INT_MAX 0x7fffffff
using namespace std;
const int maxn=101;     //点个数
int map[maxn][maxn];    //邻接矩阵
int pre[maxn][maxn];    //pre[2][3]存储最短路径3的前一个点是2
int dist[maxn][maxn];
int n;
void floyd()
{
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            dist[i][j]=map[i][j];
            pre[i][j]=i;
        }
    }
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(dist[i][k]!=INT_MAX&&dist[k][j]!=INT_MAX&&dist[i][k]+dist[k][j]<dist[i][j])
                {
                    dist[i][j]=dist[i][k]+dist[k][j];
                    pre[i][j]=pre[k][j];
                }
            }
        }
    }
}
int main()
{
    freopen("IN.TXT","r",stdin);
    scanf("%d",&n);
    int from,to,w;
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            map[i][j]=INT_MAX;
    }
    for(i=1;i<=n;i++)
    map[i][i]=0;
    while(scanf("%d%d%d",&from,&to,&w)!=EOF)
    {
        if(from==0)
        break;
        map[from][to]=w;
        map[to][from]=w;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            printf("%d  ",map[i][j]);
        printf("\n");
    }
    printf("Floyd:\n");
    floyd();
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            printf("%d  ",dist[i][j]);
        printf("\n");
    }
    cout << "Hello world!" << endl;
    return 0;
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 95
博文 49
码字总数 34362
作品 0
海淀
程序员
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
0
0
【转载】数据结构利器之私房STL

数据结构利器之私房STL 此系列的文章适合初学有意剖析STL和欲复习STL的同学们。 学过c++的同学相信都有或多或少接触过STL。STL不仅仅是c++中很好的编程工具(这个词可能有点歧义,用类库更恰...

悠米海
2012/12/02
0
0
STL vector 介绍连载1-2-3

STL简介: STL = Standard Template Library,标准模板库,惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。这可能是...

天远
2012/05/20
0
0
STL,ATL,WTL的联系与区别

STL,ATL,WTL的联系与区别 STL 即 Standard Template Library STL(标准模板库)是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时...

IMGTN
2012/06/04
0
0
CSDN回帖得分大全(近两年)

√ vs2005调用dll的时候Initialize()函数返回错误 [VC/MFC 基础类] √ 为什么我创建登陆框之后,然后获取登陆框的数据时候总是出现非法操作! [VC/MFC 界面] √ CFileFind::FindFile 支持通配...

junwong
2012/03/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

计算卷积神经网络浮点数运算量

前言 本文主要是介绍了,给定一个卷积神经网络的配置之后,如何大概估算它的浮点数运算量。 相关代码:CalFlops,基于MXNet框架的 Scala 接口实现的一个计算MXNet网络模型运算量的demo。 正文...

Ldpe2G
今天
1
0
Sql语言与MySql数据库

1. 数据库简介 1. 数据库,就是存储数据的仓库,只能通过sql语言来访问,数据库也是一个文件系统。通常,MySQL、Oracle等数据库,也被称为关系型数据库,其保存的不仅仅只是数据,还包括数据...

江左煤郎
今天
1
0
IDEA 取消自动import .*

打开设置 > Editor > Code Style > Java > Scheme Default > Imports ① 将 Class count to use import with "*" 改为 99 (导入同一个包的类超过这个数值自动变为 * ) ② 将 Names count ......

乔老哥
今天
3
0
PostGIS学习笔记(开篇)

PostGIS事实上算是笔者开始写博客的第一篇内容。而事实上那篇博文的内容并不丰富,笔者对PostGIS的了解仍然不多,然而17年在OSGeo课程学习时对PostGIS又有了进一步了解,并逐步发现它的强大。...

胖胖雕
今天
3
0
【Centos】在nginx服务器中配置php和mysql

接上一章《【Centos】利用Vultr服务器和namesilo布网》(https://my.oschina.net/u/3776619/blog/2051986),在Centos中配置好nginx,并在iptables中开启了80端口,和为了远程mysql操作方便开...

yongh701
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部