更新时间: 2016-09-23 09:20:33       分类: 算法


继续最短路径!说说Bellman—Ford算法

思路:假设起点为s,图中有n个顶点和m个边,那么它到任一点(比如i)的最短路径

最多可以有n-1条(没有回路就是n-1条);因为最短路径中不可能包含回路:如果有正权

回路(正圈),那么最短路径肯定不走这个回路(不绕圈,绕圈会增加权值,直接走),

如果有负权回路(负圈),那么就不存在最短路径,因为每走一次负圈权值就减少一次,

根本不存在最小值。 我们再次利用松弛的办法:每一轮,我们枚举所有的边,看不能不能缩短两个顶点之间的

距离。到i顶点的缩短就意味着可以经过一个另一个的顶点来缩短起点到i顶点的距离,换

句话说,最短距离多了一条边。每进行一轮松弛,最短距离就可能多一条边,而最短路径

最多有n-1条边,所以进行n-1轮次松弛就可以了。 核心代码如下: for(int k=1;k<=n-1;k++) for(int i=1;i<=m;i++) if(dis[v[i]]>dis[u[i]]+w[i]) dis[v[i]] = dis[u[i]] + w[i]; 现在分析:首先要注意的是使用该算法时,我们没有使用邻接矩阵或者邻接表。而是采用

三个数组u,v,w来记录每一条边(因为我们只利用边)。三个对应的值:u[i],v[i],w[i]

表示从u[i]到v[i]有一条权值为w[i]边。 接下来每一轮我们都枚举每一条边,来尝试能否缩短起点s到该边的终点v[i]的距离。注

意,如果s不能到达u[i],那么dis[u[i]]就是INF,这个松弛就是失败的(理解一下)。 这样的算法是有优化的余地的,我们可以看到每一轮松弛中是有失败的,也就浪费了时间

。之后还可以优化。

另外还可以用Bellman-Ford算法来计算图中是否有负圈。如果我们增加轮数为n,那么如

果第n轮有dis[]有更新就说明是有负圈的。

代码如下

# include<iostream>

using namespace std;

int dis[1000];//保存临时值(或者确定值)
int u[1000], v[1000], w[1000];

const int INF = 99999999;

int main()
{
    int n, m;//n个顶点,m条边。

    cin >> n >> m;

    for (int i = 0; i < m; i++)//读入m条边
        cin >> u[i] >> v[i] >> w[i];

    //初始化dis数组
    for (int i = 0; i < n; i++)
        dis[i] = INF;

    dis[0] = 0;//还是默认顶点0为起点s


    //Bellman-Ford算法核心
    for (int i = 0; i < n - 1; i++)//进行n轮松弛
        for (int k = 0; k < m; k++)//枚举m条边
            if (dis[v[k]] > dis[u[k]] + w[k])
                dis[v[k]] = dis[u[k]] + w[k];

    for (int i = 0; i < n; i++)
        cout << dis[i] << " ";

    system("pause");

    return 0;
}

评论

还没有评论