SPFAアルゴリズムまとめ

SPFAアルゴリズム
一、spfaアルゴリズム
多くの場合、所与の図には負権辺があります.この時Dijkstraなどのアルゴリズムは使う場所がなくなりました.Bellman-Fordアルゴリズムの複雑さが高すぎて、SPFAアルゴリズムが役に立ちました.
思想:単一ソースの最短経路を求めて、負の側面権の場合に適用できます.spfa(Shotest Path Faster Algorithm)アルゴリズムはbellman-fordアルゴリズムのキュー最適化である.先に出た列を作って最適化すべき結点を保存します.最適化する時は毎回チームの先頭結点uを取り出して、u点を離れる最短経路推定値を使って、u点から指す結点vを緩和します.v点の最短経路推定値が調整され、v点が現在の列にない場合は、v点を列の最後に入れます.このようにして、列が空になるまで、列から結点を取り出して弛緩作業を行います.
二、テンプレート
 

#include 
#include 
#include 
#include 
using namespace std;

const int N = 105;
const int INF = 0x3f3f3f3f;

int map[N][N], dist[N];
bool visit[N];
int n, m;

void init() //   
{
    int i, j;
    for (i = 1; i < N; i++)
    {
        for (j = 1; j < N; j++)
        {
            if (i == j)
            {
                map[i][j] = 0;
            }
            else
            {
                map[i][j] = map[j][i] = INF;
            }
        }
    }
}

/**
 * SPFA  .
 *   spfa          
 *     :
 * start:  
 */
void spfa(int start)
{
    queue Q;
    int i, now;
    memset(visit, false, sizeof(visit));
    for (i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }
    dist[start] = 0;
    Q.push(start);
    visit[start] = true;
    while (!Q.empty())
    {
        now = Q.front();
        Q.pop();
        visit[now] = false;
        for (i = 1; i <= n; i++)
        {
            if (dist[i] > dist[now] + map[now][i])
            {
                dist[i] = dist[now] + map[now][i];
                if (visit[i] == 0)
                {
                    Q.push(i);
                    visit[i] = true;
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        while(m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);

            if(map[a][b] > c)
            {
                map[a][b] = map[b][a] = c;
            }
        }
        spfa(1);
        printf("%d
",dist[n]);
    }
    return 0;
}

 

//    
#include  
#include 
#include 
#define Maxn 100
#define Maxm 10000
#define Max 10000
int used[Maxn],outqueue[Maxn],head[Maxn],queue[Maxn],low[Maxn],n,m;
struct Edge
{
    int to,w,next;
} edge[Maxm];
bool SPFA(int start)
{
    int i =0, iq = 0;
    used[start] = 1;
    queue[iq++] = start;
    low[start] = 0;
    while (i != iq)
    {
        int top = queue[i];
        used[top] = 0;
        outqueue[top]++;//         
        if (outqueue[top] > n) return false;
        for (int k = head[top]; k != -1; k = edge[k].next)//     
        {
            if (low[edge[k].to] > low[top] + edge[k].w)//      
                low[edge[k].to] = low[top] + edge[k].w;
            if (!used[edge[k].to])
            {
                used[edge[k].to] = 1;
                queue[iq++] = edge[k].to;
            }
        }
        i++;
    }
    return true;
}

int main()
{
    while (scanf ("%d%d", &n,&m) != EOF)
    {
        memset (used, 0,sizeof(used));
        memset (head, -1,sizeof(head));
        memset (outqueue, 0,sizeof(outqueue));
        memset (low, Max, sizeof(low));
        int k = 0;
        while (m--)
        {
            int a,b,w;
            scanf ("%d%d%d", &a, &b, &w);
            edge[k].to = b;
            edge[k].w = w;
            edge[k].next = head[a];
            head[a] = k++;
        }
        if (SPFA(1))
            printf ("%d
", low[n]);
        else
            printf ("     
");
    }
}

 

// stl    
#include 
#include 
#include 
#include 
#define Maxn 100
#define Maxm 10000
#define Max 10000
using namespace std;
int used[Maxn],outqueue[Maxn],head[Maxn],low[Maxn],n,m;
struct Edge
{
    int to,w,next;
} edge[Maxm];
bool SPFA (int start)
{
    queue  a;
    used[start] = 1;
    low[start] = 0;
    a.push(start);
    while (!a.empty())
    {
        int top = a.front();
        a.pop();
        outqueue[top]++;
        if (outqueue[top] > n) return false;
        for (int k = head[top]; k!= -1; k = edge[k].next)
        {
            if (low[edge[k].to] > low[top] + edge[k].w)
                low[edge[k].to] = low[top] + edge[k].w;
            if (!used[edge[k].to])
            {
                used[edge[k].to] = 1;
                a.push(edge[k].to);
            }
        }
    }
    return true;
}

int main()
{
    while (scanf ("%d%d", &n,&m) != EOF)
    {
        memset (used, 0,sizeof(used));
        memset (head, -1,sizeof(head));
        memset (outqueue, 0,sizeof(outqueue));
        memset (low, Max, sizeof(low));
        int k = 0;
        while (m--)
        {
            int a,b,w;
            scanf ("%d%d%d", &a, &b, &w);
            edge[k].to = b;
            edge[k].w = w;
            edge[k].next = head[a];
            head[a] = k++;
        }
        if (SPFA(1))
            printf ("%d
", low[n]);
        else
            printf ("     
");
    }
}