文档章节

Bellman - Ford算法c++实现(前向星)

侯禹
 侯禹
发布于 2013/09/24 23:38
字数 275
阅读 302
收藏 2
/*   Bellman - Ford   */
#include <iostream>
#include <cstdio>
#include <cstring>
#define Inf 0x7fffffff
#define MaxV 10000
#define MaxE 10000
using namespace std;
int N,M;
struct Edge
{
    int to,next,w;
}edge[MaxE];
int size,head[MaxV];
void InsertEdge(int from,int to,int w)
{
    edge[size].to=to;
    edge[size].w = w;
    edge[size].next=head[from];
    head[from]=size++;
}
int dist[MaxV];
bool bellmanFord(int s)
{
    int i,j,k;
    int to;
    for(i=1;i<=N;i++)
        dist[i]=Inf;
    dist[s]=0;
    for(i=1;i<=N-1;i++)                     //每个点都更新N-1 次
    {
        for(j=1;j<=N;j++)           //每个点更新一次
        {
            if(dist[j]==Inf)    continue;   //如果不能到达,则下一个点
            for(k=head[j];k+1;k=edge[k].next)
            {
                to=edge[k].to;
                if(edge[k].w!=Inf&&dist[to]>dist[j]+edge[k].w)
                    dist[to]=dist[j]+edge[k].w;
            }
        }
    }
    for(j=1;j<=N;j++)
    {
        if(dist[j]==Inf)    continue;   //如果不能到达这个点
        for(k=head[j];k+1;k=edge[k].next)
        {
            to=edge[k].to;
            if(edge[k].w!=Inf&&dist[to]>dist[j]+edge[k].w)
                return false;
        }
    }
    return true;
}
void init()
{
    int from,to,w;
    scanf("%d%d",&N,&M);
    size=0;
    memset(head,-1,sizeof(head));
    for(int i=0;i<M;i++)
    {
        scanf("%d%d%d",&from,&to,&w);
        InsertEdge(from,to,w);
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    init();
    if(bellmanFord(1)) printf("OK");
    else printf("No");
    return 0;
}


© 著作权归作者所有

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

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

索隆
2011/12/03
0
0
初学图论-Bellman-Ford单源最短路径算法

本文使用C++实现了这一基本算法。参考《算法导论》第24.1节 笔者使用了vector实现邻接链表,以提高运行效率。 /** * Bellman-Ford's Single Source Shortest Path Algorithm in C++ * Time C...

不高不富不帅的陈政_
2015/08/06
0
0
C语言/C++编程学习—绘制神奇代码之星空动态

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/03/26
0
0
开发者应该开始学习 C++ 吗?

随着C++ 11和C++ CX的引入,很多人重新燃起了对这门语言的兴趣。不少开发者,尤其是Windows开发者,都想知道是否应该放弃C#和Java,转而支持C++。John Sonmez认为这并不需要。 在“为什么C++...

戴威
2012/12/26
8.6K
44
泛型编程与设计新思维

作者: 徐景周 转帖: http://www.vckbase.com/document/viewdoc/?id=955 前言 永远记住,编写代码的宗旨在于简单明了,不要使用语言中的冷僻特性,耍小聪明,重要的是编写你理解的代码,理解...

ValueError
2011/01/12
339
1

没有更多内容

加载失败,请刷新页面

加载更多

数据库篇多表操作

第1章 多表操作 实际开发中,一个项目通常需要很多张表才能完成。例如:一个商城项目就需要分类表(category)、商品表(products)、订单表(orders)等多张表。且这些表的数据之间存在一定的关系...

stars永恒
59分钟前
2
0
nginx日志自动切割

1.日志配置(Nginx 日志) access.log----记录哪些用户,哪些页面以及用户浏览器,IP等访问信息;error.log------记录服务器错误的日志 #配置日志存储路径:location / {      a...

em_aaron
昨天
3
0
java 反射

基本概念 RTTI,即Run-Time Type Identification,运行时类型识别。RTTI能在运行时就能够自动识别每个编译时已知的类型。   要想理解反射的原理,首先要了解什么是类型信息。Java让我们在运...

细节探索者
昨天
1
0
推荐转载连接

https://www.cnblogs.com/ysocean/p/7409779.html#_label0

小橙子的曼曼
昨天
3
0
雷军亲自打造的套餐了解下:用多少付多少

12月28日消息,小米科技创始人兼CEO雷军微博表示,小米移动任我行套餐方案,原则上就是明明白白消费,用多少付多少,不用不花钱!上网、电话和短信都是一毛钱,上网0.1元/M,电话0.1元/分钟,...

linuxCool
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部