bellman-ford的理解

﹏ヽ暗。殇╰゛Y 2022-06-15 12:36 45阅读 0赞

迪杰斯特拉算法由于贪心的思想无法处理负权的问题，就要用到贝尔曼福德算法了，这个也是一个单源最短路算法，主要思想最多进行n-1循环，每次遍历所有的边，进行松弛操作，如果遍历了一遍没有松弛操作说明已经是最短了，就退出

下面是一道例题：

## 1305: 最短路 ##

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld  
Submitted: 118 Accepted: 50  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

## Input ##

第一行两个整数n, m。

接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

## Output ##

共n-1行，第i行表示1号点到i+1号点的最短路。

## Sample Input ![copy.gif][] ##

3 3
    1 2 -1
    2 3 -1
    3 1 2

##     ##

## Sample Output ##

-1
    -2

## HINT ##

数据规模与约定

对于10%的数据，n = 2，m = 2。

对于30%的数据，n <= 5，m <= 10。

对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

示范代码：

#include<stdio.h>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<string>
    using namespace std;
    int m,n,tot;
    const int INF=1008611;//就是那么任性qwq
    struct edge
    {
        int from,to;
        int v;
    };
    edge e[200005];
    int dis[20005];
    void init()//初始化1到各个点的距离为inf
    {
        int i,j;
        for(i=1;i<=n;i++)
        {
            dis[i]=INF;
        }
        dis[1]=0;//到自己的距离为0
        tot=0;
    }
    void add(int f,int t,int v)//用于加入边的情况
    {
        e[tot].to=t;
        e[tot].from=f;
        e[tot].v=v;
        tot++;
    }
    int main()
    {
        int i,j,k,x,y,z,tag;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            init();
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&x,&y,&z);
                add(x,y,z);
                if(x==1)
                    dis[y]=z;//如果x就是1的话就直接初始化 
            }
            for(i=1;i<=n-1;i++)//最多n-1次
            {
                tag=0;
                for(j=0;j<tot;j++)
                {
                    if(dis[e[j].to]>dis[e[j].from]+e[j].v)//松弛操作
                    {
                        dis[e[j].to]=dis[e[j].from]+e[j].v;
                        tag=1;
                    }
                }
                if(!tag)//没有松弛退出
                    break;
            }
            for(i=2;i<=n;i++)//输出从1到各节点的最短路
                printf("%d\n",dis[i]);
        }
        return 0;
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=1305&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=1305&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=1305&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif