文档章节

floyd算法c++

侯禹
 侯禹
发布于 2013/09/25 20:03
字数 246
阅读 82
收藏 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;
}


© 著作权归作者所有

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

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

索隆
2011/12/03
0
0
POJ ~ 2240 ~ Arbitrage (Floyd或BellmanFord)

题意:你现在有N种类型的货币,这N种类型的货币之间有M种汇率关系,然后输入M组关系,A,rate,B,表示每单位A货币可以换rate的B货币。问你有没有方法使自己的钱增多? 思路:判断是否正环。...

ZscDst
01/30
0
0
STL list链表的用法详解

------------------------------------------------------------------------------- 原来... STL list链表的用法详解 本文以List容器为例子,介绍了STL的基本内容,从容器到迭代器,再到普通...

nao
2014/04/10
0
0
C#转C++的一点分享

从C#转C++有段时间了,一直想分享点什么,但又不太好意思分享,毕竟自己做C++的时间不太长,最近感觉自己已能胜任现有工作,想分享的想法又强了点,前几天看到这样一篇博客《那些年·我们读过的专业...

爱情经纬线
2014/01/17
3.7K
10
看完这 7 条,模拟 C++ 新功能只是一个小目标!

但是,即使你无法使用这些功能,也不一定要放弃它们的好处。至少不用放弃全部。 有一些方法可以使用代码中新功能的思路,更准确地传达你的意图。 当然,这些方法肯定不如使用新版本C++本身的...

CSDN资讯
09/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

对接比特币钱包的PHP开发包

BtcTool是一个基于第三方服务和离线裸交易实现的PHP比特币应用开发包,适合不希望部署本地 节点旳PHP开发者,开发包主要包含以下特性: 利用第三方服务获取指定地址的utxo集合 离线生成消费裸...

汇智网教程
7分钟前
0
0
【自用】 VHD to VHDX

VHDX: 在VHD 2TB 的基础上提供 64TB的容量。 支持逻辑扇区大小为 4KB,和每块的大小为 256MB,来优化虚拟磁盘性能。 比VHD提供更高的安全性、可靠性和性能。 convert-VHD –path d:\Hyper-v...

Tensor丨思悟
20分钟前
0
0
30 岁转行做Python开发晚吗?而且是零基础

最近有小伙伴问小编,30 岁转行做Python开发晚吗? 小编想说,其实无论男女,只要想学,有这个动力,就直接去行动。无论年龄,无论性别,只要你想一直勇往直前,那么想做的就去做吧~这里有一...

糖宝lsh
30分钟前
7
0
详解Spring中的Profile

前言 由于在项目中使用Maven打包部署的时候,经常由于配置参数过多(比如Nginx服务器的信息、ZooKeeper的信息、数据库连接、Redis服务器地址等),导致实际现网的配置参数与测试服务器参数混淆...

watermelon11
45分钟前
4
0
phper必知必会(二)

  1.说说你对进程,线程以及协程的理解      进程:是系统进行资源分配和调度的基本单位,是基本操作系统结构的基础。进程是程序基本执行的实体。进程与进程之间是独立的,拥有完全独立...

SEOwhywhy
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部