文档章节

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

侯禹
 侯禹
发布于 2013/09/24 23:38
字数 275
阅读 296
收藏 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++的迪杰斯特拉
侯禹
粉丝 95
博文 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语言编程入门学习:用C语言输出九九乘法表

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

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

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

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

没有更多内容

加载失败,请刷新页面

加载更多

小白带你认识netty(三)之NioEventLoop的线程(或者reactor线程)启动(一)

在第一章中,我们看关于NioEventLoopGroup的初始化,我们知道了NioEventLoopGroup对象中有一组EventLoop数组,并且数组中的每个EventLoop对象都对应一个线程FastThreadLocalThread,那么这个...

天空小小
今天
3
0
PHP动态扩展Redis模块

查看已有模块 [root@test-a ~]# /usr/local/php/bin/php -m[PHP Modules]bz2Core...zlib[Zend Modules] 下载包,解压,生成configure文件 [root@test-a ~]# cd /usr/local/src/[ro......

野雪球
今天
3
0
在Ignite中使用线性回归算法

在本系列前面的文章中,简单介绍了一下Ignite的机器学习网格,下面会趁热打铁,结合一些示例,深入介绍Ignite支持的一些机器学习算法。 如果要找合适的数据集,会发现可用的有很多,但是对于...

李玉珏
今天
4
0
Mybatis应用学习——简单使用示例

1. 传统JDBC程序中存在的问题 1. 一个简单的JDBC程序示例: public class JDBCDemo {public static void main(String[] args) {Connection con=null;PreparedStatement statemen...

江左煤郎
今天
4
0
使用JavaScript编写iOS应用业务逻辑

JSAUIKitCocoa使你可以使用JavaScript编写对性能要求不高但可能变动性很大的iOS应用的业务逻辑部分,View组件、需要多线程支持的Model等则直接使用原生对象。 编写方式与React Native相似,但...

neal01
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部