原 初学图论-Bellman-Ford单源

    本文使用C++实现了这一基本算法。参考《算法导论》第24.1节

    笔者使用了vector实现邻接链表,以提高运行效率。

/**
 * Bellman-Ford's Single Source Shortest Path Algorithm in C++
 * Time Cost : O(|N||M|)
 * Introduction to Algorithms (CLRS) 24.1
 * Author: Zheng Chen / Arclabs001
 * Copyright 2015 Xi'an University of Posts & Telecommunications
 */
#include <iostream>
#include <vector>
#include <fstream>
#define INF 0xfffffff
using namespace std;
const int N = 5;
const int M = 10;
ifstream in;

struct edge
{
    int dest;
    int weight;
};

struct vertex
{
    int num;
    int dist;
    int inDegree,outDegree;
    vertex * parent;
}V[N];

vector<edge> AdjList[N];
bool changes; //To check if there is changes in the loop
//Suppose the longest way has m edges, so the distance will not change after
//m loops, so that we can terminate the loop after m+1 times.

void initialize(int s)
{
    for(int i=0; i<N; i++)
    {
        V[i].num = i;
        V[i].dist = INF;
        V[i].parent = nullptr;
        V[i].inDegree = 0;
        V[i].outDegree = 0;
        AdjList[i].clear();
    }

    for(int i=0; i<M; i++)  //Read informations of edges and insert into the Adjacent List
    {
        int _start, _dest, _weight;
        edge * tmp = new edge;

        in>>_start>>_dest>>_weight;
        tmp->dest = _dest;
        tmp->weight = _weight;
        V[_start].outDegree++;
        V[_dest].inDegree++;

        AdjList[_start].push_back(*tmp);
    }

    V[s].dist = 0;
}

void relax(int u, int v, int weight)  //The "relax" operation
{
    if(V[v].dist > V[u].dist + weight)
    {
        V[v].dist = V[u].dist + weight;
        V[v].parent = &V[u];
        changes = true;
    }
}

bool bellman_ford(int s)
{
    changes = true;
    initialize(s);

    for(int k=1; k<N && changes; k++)
    {
        changes = false;
        //"Relax" the whole graph for N-1 times
        for(int i=0; i<N; i++)
        {
            edge tmp;
            for(int j=0; j<V[i].outDegree; j++)
            {
                tmp = AdjList[i][j];
                relax(i,tmp.dest,tmp.weight);
            }
        }
    }

    //Check if there is a negative circle
    for(int i=0; i<N; i++)
    {
        edge tmp;
        for(int j=0; j<V[i].outDegree; j++)
        {
            tmp = AdjList[i][j];
            if(V[tmp.dest].dist > V[i].dist + tmp.weight)
                return false;
        }
    }
    return true;
}

int main()
{
    in.open("Bellman_Ford.txt");
    if(bellman_ford(0))
    {
        cout<<"Succeed ! The distance of each vertex are :"<<endl;
        for(int i=0; i<N; i++)
        {
            cout<<V[i].dist<<" ";
        }
        cout<<endl<<"Their parents are :";
        for(int i=1; i<N; i++)
        {
            cout<<V[i].parent->num<<" ";
        }
    }
    else
    {
        cout<<"Failed ! There are at least one negative circle !"<<endl;
    }
    return 0;
}

/*
Pseudo-Code:

Initialize-Single-Source(G,s)
{
    for each vertex v in G.V
        v.d = INF
        v.parent = NIL
    s.d = 0
}

Relax(u,v,w)
{
    if(v.d > u.d + w(u,v))
        v.d = u.d + w(u,v)
        v.parent = u
}

Bellman-Ford(G,w,s)
{
    Initialize-Single-Source(G,s)
    for i=1 to |G.V|-1
        for each vertex (u,v) in G.E
            Relax(v,u,w)

    for each edge (u,v) in G.E
        if(v.d > u.d + w(u,v))
            return FALSE
    return TRUE
}
*/

//Bellma-Ford文件内容如下:

0 1 6

0 3 7

1 2 5

1 3 8

1 4 -4

2 1 -2

3 2 -3

3 4 9

4 2 7

4 0 2

每一行的三个元素分别表示某条边的起始节点、终止节点、这条边的权重。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

使用R包genefu来根据基因集进行表达谱分类

教程略微有点复杂:https://rdrr.io/bioc/genefu/f/inst/doc/genefu.pdf

2224
来自专栏机器学习从入门到成神

哥伦布编码

哥伦布编码解码 UINT GetUeValue(BYTE *pBuff, UINT nLen, UINT &nStartB...

2082
来自专栏WOLFRAM

Mma粉丝分享:全国建模大赛B题【椭圆形活动桌面设计】 by 银色子弹

1213
来自专栏从流域到海域

迪杰斯特拉(Dijkstra)算法求图中最短路径

迪杰斯特拉(Dijkstra )算法: 对于图G=(V,E),将图的顶点分为两组: 顶点集S:已求出的最短路径的顶点集合(初始为{v0}); 顶...

2277
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[03]:熟练图元绘制,玩转二维图形

文章的大前提是,你得有《OpenGL ES 2.0 (iOS): 一步从一个小三角开始》的基础知识。

2141
来自专栏图形学与OpenGL

实验5 运算符重载

1932
来自专栏Python绿色通道

数据分析 | Numpy进阶

切片索引Numpy中选取数据子集或者单个元素的方式有很多,一维数组和Pyhon列表的功能差不多,看下图:

1291
来自专栏何俊林

如何学习OpenGL Shader开发?

shader也称着色器,着色器是运行在GPU上的小程序,着色器是一种C风格语言——GLSL。

2812
来自专栏蜉蝣禅修之道

Max-Min Fairness带宽分配算法

2266
来自专栏ml

HDUOJ-------- Fibonacci again and again

   Fibonacci again and again Time Limit : 1000/1000ms (Java/Other)   Memory Limi...

35611

扫码关注云+社区

领取腾讯云代金券