在Bellman-Ford算法中 我们可以看到大量的优化空间:如果一个点的最短路径已经确定了,那么它就不会再改变,因此不需要再处理。换句话说:我们每次只对最短路径改变了的顶点的所有出边进行操作
使用一个队列就可以实现这个“轮流处理“的效果:
具体操作:选取一个顶点,入队,枚举它的出边,进行松弛,把松弛后最短距离改变的点入队,然后将最初选取的顶点(队首)出队,对新的队首顶点重复上述操作。
注意:队列中同一时刻不能有两个相同的顶点,因此如果要入队的顶点已经在队列中就不再将其入队,这就需要一个标记数组来实现。
引入C++STL中的vector和queue,写出代码如下:
/*队列优化的bellman-ford算法*/
# include<iostream>
# include<queue>
# include<algorithm>
# include<vector>using namespace std;const int MAXN = ;
const int INF = ;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 = ; i < m; i++)
{
cin >> t >> temp.to >> temp.cost;
e[t].push_back(temp);
}//输入,初始化邻接表 //初始化dis数组
for (int i = ; i <= n; i++)
{
dis[i] = INF;
} dis[] = ;//首顶点到它的距离就是0 q.push();//0号顶点入队
book[] = ;//标记已经入队 //下面这个循环就是算法的核心部分
while (!q.empty())//当列表不为空时进行
{
for (int i = ; 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] == )
{
book[e[q.front()][i].to] = ;
q.push(e[q.front()][i].to);//入队
}
}
} book[q.front()] = ;
q.pop();//出队
} for (int i = ; i <= n; i++)
cout << dis[i] << " ";
cout << endl; system("pause"); return ;}
注意:引用vector后一定不能乱。。不能晕。。。