文档章节

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

侯禹
 侯禹
发布于 2013/09/24 23:38
字数 275
阅读 287
收藏 2
点赞 0
评论 0
/*   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;
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 94
博文 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程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
03/26
0
0
C++ STL编程轻松入门 1

作为C++标准不可缺少的一部分,STL应该是渗透在C++程序的角角落落里的。STL不是实验室里的宠儿,也不是程序员桌上的摆设,她的激动人心并非昙花一现。本教程旨在传播和普及STL的基础知识,若...

暖冰
2015/11/21
0
0
CSDN回帖得分大全(近两年)

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

junwong
2012/03/09
0
0
【转载】数据结构利器之私房STL

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

悠米海
2012/12/02
0
0
C语言编程入门学习:用C语言输出九九乘法表

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

小辰带你看世界
05/29
0
0
C语言/C++永远都不会过时的编程语言

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

小辰带你看世界
03/30
0
0
C语言/C++编程学习强势之处的体现

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

小辰带你看世界
05/12
0
0
C语言/C++编程学习未来之路

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

小辰带你看世界
03/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Python爬虫 爬取百合网的女人们和男人们

学Python也有段时间了,目前学到了Python的类。个人感觉Python的类不应称之为类,而应称之为数据类型,只是数据类型而已!只是数据类型而已!只是数据类型而已!重要的事情说三篇。 据书上说...

p柯西
7分钟前
0
0
在Java中,你真的会日期转换吗

1.什么是SimpleDateFormat 在java doc对SimpleDateFormat的解释如下: SimpleDateFormatis a concrete class for formatting and parsing dates in a locale-sensitive manner. It allows fo......

Java小铺
16分钟前
0
0
Linux系统梳理---系统搭建(二):tomcat的安装和使用

上一章讲到JDK的安装使用,这一章主要记录下服务器tomcat的安装以及部署一个项目. 1.下载tomcat,这里下载的是apache-tomcat-8.5.32.tar.gz 2.创建文件夹,便于管理,和JDK一样,在usr目录下创建t...

勤奋的蚂蚁
26分钟前
0
0
ES15-聚合

1.Terms Aggregation 分组聚合 2.Filter Aggregation 过滤聚合

贾峰uk
28分钟前
0
0
【2018.07.19学习笔记】【linux高级知识 20.27-20.30】

20.27 分发系统介绍 20.28 expect脚本远程登录 20.29 expect脚本远程执行命令 20.30 expect脚本传递参数

lgsxp
30分钟前
0
0
10.32/10.33 rsync通过服务同步~10.35 screen工具

通过服务的方式同步要编辑配置文件:[root@linux-xl ~]# vim /etc/rsyncd.confport=873log file=/var/log/rsync.logpid file=/var/run/rsyncd.pidaddress=192.168.43.21[tes...

洗香香
33分钟前
0
0
与女儿谈商业模式 (3):沃尔玛的成功模式

分类:与女儿谈商业模式 | 标签: 经济学 沃尔玛 陈志武 2007-05-10 09:09阅读(11279)评论(30) 与女儿谈商业模式 (3):沃尔玛的成功模式 陈志武 /文 沃尔玛(Wal-Mart)是另一个有意思的财...

祖冲之
40分钟前
0
0
网页加载速度优化方法总结

1、减少请求 最大的性能漏洞就是一个页面需要发起几十个网络请求来获取诸如样式表、脚本或者图片这样的资源,这个在相对低带宽和高延迟的移动设备连接上来说影响更严重。 2、整合资源 对开发...

Jack088
46分钟前
0
0
dubbo学习

https://blog.csdn.net/houshaolin/article/details/76408399

喵五郎
58分钟前
0
0
mybatis-session.selectList源码分析

0.构建工厂:SqlSessionFactory 。 new SqlSessionFactoryBuilder.build(配置的xml文件) 获取sqlSession对象 //指定事务隔离级别 1. sqlMapper.openSession(TransactionIsolationLevel.SER......

writeademo
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部