[数据结构与算法]C++队列优化的bellman算法

普通的bellman算法如下

	for(int i=1;i<=n-1;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(dis[v[j]]>dis[u[j]]+w[j])
			{
				dis[v[j]]=dis[u[j]]+w[j];
			}
		}
	}

此处需进行n-1次循环来判断是否已经达到最短路径，但其实有些点在n-1之前已经求得最短路径了，所以采用队列+邻接表来进行优化，把一个顶点的所有出边全都处理完了，然后把这个点出队即可。因为很可能不会再利用这个顶点来松弛了(出边都用完了)。

//核心代码
while(q.size()!=0)//队列不为0时就说明有的点没处理完
 {
  k=first[q.front()];//从队首的第一条边开始
  while(k!=0)
  {
   if(dis[v[k]]>dis[u[k]]+w[k])
   {
    dis[v[k]]=dis[u[k]]+w[k];//松弛
    if(b[v[k]]==0)//这是一个标记数组，要是b[i]=1就不用再入队了
    {
     q.push(v[k]);
     b[v[k]]=1;
    }
   }
  k=next[k];
  b[q.front()]=0;//把队首的b[i]标记为0，以便下次再进入队列
  //再进入队列是因为可能有到次顶点的边，例如点3的出边遍历完了
  //但是有可能还有2 3 1，这样 到3 的边
  //这时候可能3的最短路径会发生变化，需要重新松弛其所有出边
  q.pop();//把队首出队
  }
 }

完整代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
 int n,m,inf=99999;
 queue <int> q;
 int u[100],v[100],w[100];
 int first[100]={0},next[100]={0};
 int dis[100],b[100]={0};
 cin>>n>>m;
 for(int i=2;i<=n;i++)
 {
  dis[i]=inf;
 }
 dis[1]=0;
 for(int i=1;i<=m;i++)
 {
  cin>>u[i]>>v[i]>>w[i];
  next[i]=first[u[i]];
  first[u[i]]=i;
 }
 q.push(1);
 b[1]=1;
 int k;
 while(q.size()!=0)
 {
  k=first[q.front()];
  while(k!=0)
  {
   if(dis[v[k]]>dis[u[k]]+w[k])
   {
    dis[v[k]]=dis[u[k]]+w[k];
    if(b[v[k]]==0)
    {
     q.push(v[k]);
     b[v[k]]=1;
    }
   }
  k=next[k];
  b[q.front()]=0;
  q.pop();
  }
 }
 for(int i=1;i<=n;i++)
 {
  cout<<dis[i]<<" ";
 }
 return 0;
}

样例
5 7
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6