更新时间: 2016-09-23 14:42:32       分类: 算法


在Bellman-Ford算法中 我们可以看到大量的优化空间:如果一个点的最短路径已经确定了,那么它就不会再改变,因此不需要再处理。换句话说:我们每次只对最短路径改变了的顶点的所有出边进行操作

使用一个队列就可以实现这个“轮流处理“的效果:

具体操作:选取一个顶点,入队,枚举它的出边,进行松弛,把松弛后最短距离改变的点入队,然后将最初选取的顶点(队首)出队,对新的队首顶点重复上述操作。

注意:队列中同一时刻不能有两个相同的顶点,因此如果要入队的顶点已经在队列中就不再将其入队,这就需要一个标记数组来实现。

引入C++STL中的vector和queue,写出代码如下:

/*队列优化的bellman-ford算法*/
# include<iostream>
# include<queue>
# include<algorithm>
# include<vector>

using namespace std;

const int MAXN = 100;
const int INF = 99999999;

int book[MAXN], dis[MAXN];

int n, m;//n是顶点数,m是边数,默认顶点编号从1开始

struct edge
{
    int to;
    int cost;
};//边的定义

queue <int> q;


int main()
{
    int t;
    struct edge temp;
    vector <edge> e[MAXN];

    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> t >> temp.to >> temp.cost;
        e[t].push_back(temp);
    }//输入,初始化邻接表
    
    //初始化dis数组
    for (int i = 1; i <= n; i++)
    {
        dis[i] = INF;
    }

    dis[1] = 0;//首顶点到它的距离就是0

    q.push(1);//0号顶点入队
    book[1] = 1;//标记已经入队

    //下面这个循环就是算法的核心部分
    while (!q.empty())//当列表不为空时进行
    {
        for (int i = 0; i < e[q.front()].size(); i++)//枚举队首节点的所有出边
        {

            if (dis[e[q.front()][i].to] > dis[q.front()] + e[q.front()][i].cost)
            {
                dis[e[q.front()][i].to] = dis[q.front()] + e[q.front()][i].cost;
                //说明队首节点的第i条出边所指向的顶点的最小值可以更新
                if (book[e[q.front()][i].to] == 0)
                {
                    book[e[q.front()][i].to] = 1;
                    q.push(e[q.front()][i].to);//入队
                }
            }
        }

        book[q.front()] = 0;
        q.pop();//出队
    }

    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    cout << endl;
    
    system("pause");

    return 0;

}

评论

还没有评论