單源最短路徑 ——SPFA算法

求單源最短路徑的SPFA算法在Bellman-Ford算法的基礎上進行了改進，使其在能夠計算帶負權圖的單源最短路徑的基礎上，時間複雜度大幅度降低。

時間複雜度   O(k*e)  k<=2

基本算法：

    設立一個先進先出的隊列來儲存待優化的節點，優化時每次取出隊首節點u，并且用u點目前的最短路徑估計值對離開u點所指向的節點v進行松弛操作，如果v點的最短路徑估計值有所調整，且v點不在目前的隊列中，就将v點放入隊尾。這樣不斷從隊列中取出節點來進行松弛操作，直至隊列空為止。這個算法保證隻要最短路徑存在，SPFA算法必定能求出最小值。

    SPFA算法同樣可以判斷負環，如果某個點彈出隊列的次數超過N-1次，則存在負環。對于存在負環的圖，無法計算單源最短路徑。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 1010
int n,m,k,a,b,c,s,e;
int map[maxn][maxn],pre[maxn],vis[maxn],dist[maxn],lj[maxn];
void spfa(int s)
{
    for(int i=0;i<=n;i++)
    {
        dist[i]=INF;  pre[i]=s;
    }
    dist[s]=0; pre[s]=-1;
    memset(vis,0,sizeof(vis));
    queue<int>q;
    while(!q.empty()) q.pop();
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int v=1;v<=n;v++)
        {
            if(dist[v]=dist[u]+map[u][v])
            {
                dist[v]=dist[u]+map[u][v];
                pre[v]=u;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            map[i][j]=INF;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(map[a][b]>c)
                map[a][b]=map[b][a]=c;
        }
        scanf("%d%d",&s,&e);
        spfa(s);
        printf("%d\n",dist[e]);
    }
    return 0;
}