初级算法-Bellman-ford算法

参考一：啊哈算法

参考：https://blog.csdn.net/u010087886/article/details/46316483

一、Bellman-Ford算法：

求解边上带有负值的单源最短路径问题
Bellman(贝尔曼)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法。

Bellman-ford算法是求解连通带权图中单源最短路径的一种常用算法，它允许图中存在权值为负的边。
同时它还能够判断出图中是否存在一个权值之和为负的回路。如果存在的话，图中就不存在最短路径

举例分析

https://blog.csdn.net/Houson_c/article/details/72568976

image.png

//求顶点1到其他顶点的最短路径，
//最短路径结果记录到distance数组中
distance[5] = {0,1000,1000,1000,1000}//1000为极大值

//遍历所有边得到经过一条边后distance数组为

队列优化

队列优化最核心的思想就是：
每次仅对最短路径估计值发生了变化的顶点的所有出边执行松弛操作。

每次选取队首顶点u，对顶点的所有出边进行松弛操作。例如有一条u→v的边，如果通过u→v这条边是的源点到顶点v的最短路程变短，且顶点v不在当前的队列中，就将顶点v放入队尾。需要注意的是，同一个顶点同时在队列中出现多次是毫无意义的，所以我们需要一个数组来判重。在对顶点u的所有出边松弛完毕后，就将顶点u出队。

#include<iostream>
using namespace std;
#define INF 999999
int main ()
{
    int dis[6],que[101]={0},book[6];
    int first[10],next[10];
    int u[8],v[8],w[8];
    int head=1,tail=1;
    int s,n,m,i;
//
    cout << "please input the number of the  city: ";
    cin >> n;
    cout << "is there how many roads: ";
    cin >> m;
    cout << "please input the start: ";
    cin >> s;
    cout << "please input the information of the roads: ";
//初始化矩阵
     for(i=1;i<=n;++i)
        dis[i]=INF;
//起始点
    dis[s]=0;
//初始化book数组
    for(i=1;i<=n;++i)
        book[i]=0;
//初始化队列
    for(i=1;i<=n;++i)
        first[i]=-1;
//
    for(i=1;i<=m;++i)
    {
        cin >> u[i] >> v[i] >> w[i];
        next[i]=first[u[i]];
        first[u[i]]=i;
    }
    que[tail]=s;
    ++tail;
    book[s]=1;
        while(head < tail)
    {
        int k;
        k=first[que[head]];
        while(k != -1)
        {
            if(dis[v[k]]>(dis[u[k]]+w[k]))
            {
                dis[v[k]]=dis[u[k]]+w[k];
                if(book[v[k]] == 0)
                {
                    que[tail]=v[k];
                    ++tail;
                    book[v[k]]=1;
                }
            }
            k=next[k];
        }
        book[que[head]]=0;
        ++head;
    }
    for(i=1;i<=n;++i)
        cout << dis[i] << " ";
    return 0;
}