原理：队列+松弛操作
将源点加入队尾，每一步读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新距离（即令d[v]变小），那么就更新，另外，如果点v没有在队列中（打个标记），那么要将点v入队，如果已经在队列中了，那么就不用入队
以此循环，直到队空为止就完成了单源最短路的求解
判断有无负环：
如果某个点进入队列的次数超过N次则存在负环
/**************************************************************************************************** 最短路—Bellman-Ford算法队列优化(SPFA)邻接表 将边权替换为概率，相加改为相乘，最短距离改为最大概率 ********************************************************************************************************/ #include<cstdio> #include<queue> #define maxint 99999999 #define maxn 10005 #define eps 1e-8 using namespace std; struct Edge{ int next,to; double power; }e[maxn*6];//保存边 double dist[maxn];// 结点到源点最小距离(最大概率) int ed[maxn];//邻接表 int n,m,source=1,c[maxn];// 结点数，边数，源点,记录进队次数 bool vis[maxn];//判断是否在队列中 queue<int> q; void in(){// 初始化图 scanf("%d%d",&n,&m);// 输入结点数，边数 for(int i=1;i<=n;i++)dist[i]=0;//初始化刚开始距离为最大(概率为最小) dist[source]=1;//到源点最小距离为0(概率为1) int x,j; for(int i=1;i<=m;i++){ j=i<<1; scanf("%d%d%lf",&x,&e[j].to,&e[j].power);e[j].power/=100; e[j].next=ed[x];ed[x]=j; e[j+1].to=x;e[j+1].next=ed[e[j].to];ed[e[j].to]=j+1;e[j+1].power=e[j].power; } }bool SPFA(int s){ q.push(s);vis[s]=1,c[s]=1; while(!q.empty()){ int x=q.front();q.pop();vis[x]=0; int i=ed[x]; while(i){ int j=e[i].to; if(dist[x]*e[i].power-eps>dist[j]){ dist[j]=dist[x]*e[i].power;//松弛 vis[j]=1;//标记 c[j]++;q.push(j);//入队 if(c[j]>n)return 0;//有负环 } i=e[i].next; } } return 1; } int Perseverance(){ freopen("toura.in","r",stdin); freopen("toura.out","w",stdout); in(); if(SPFA(1)) printf("%.6lf",dist[n]*100); return 0; } int comeon=Perseverance(); int main(){ return 0; }
两个优化
SLF（Small Label First）： 设要加入的节点是j，队首元素为i，若dist(j) < dist(i)，则将j插入队首，否则插入队尾。
LLL（Large Label Last）：设队首元素为i，每次弹出时进行判断，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。