Bellman-ford队列优化算法的核心在于
：继承了bellman-ford算法的核心内容（邻接表处理）
利用队列优化，减少了不必要的判断
下面在代码中进行详解
#include"iostream"
#include"cstdio"
#define inf 9999999
using namespace std;
int u[100]; //u,v,w为邻接表存储边信息的必要数组空间
int v[100];
int w[100];
int dis[100]; //记录源点到其余个点的最短路
int first[100]; //记录i为起点的第一个边的编号
int next[100]; //记录i号边的下一条边的编号
int n,m;
int book[100]; //判重是否点已经进入队列
int queue[100]; //队列
int head;
int tail;
int k;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) //dis初始化
{
dis[i]=inf;
}
dis[1]=0;
for(int i=1;i<=n;i++) //first初始化
{
first[i]=-1;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u[i],&v[i],&w[i]); //边的录入
next[i]=first[u[i]];
first[u[i]]=i;
}
queue[1]=1;
head=1;
tail=2;
book[1]=1;
while(head<tail)
{
k=first[queue[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)
{
book[v[k]]=1;
queue[tail]=v[k];
tail++;
}
}
k=next[k];
}
head++;
book[queue[head]]=0;
}
for(int i=1;i<=n;i++)
{
printf("%d ",dis[i]);
}
return 0;
}