単一ソース最短SPFAアルゴリズムテンプレート

概要

図論では、最短路は非常に重要な一部であり、多くの問題で

に関連している.

現在のSPFAアルゴリズムは非常に優れたアルゴリズムであり,時間的複雑度はO(k∗E)

である.

ここで、Eは図の辺数であり、kは定数であり、一般に極小である.

実際にSPFAはBellman-fordアルゴリズムにキュー最適化を加えて冗長な緩和動作を低減し,効率的な最短回路アルゴリズムである.

しかもSPFAは負のループを判定することができて、この情況の下でDijkstraのアルゴリズムなどの武を使う場所がなくなりました!

使用法

はキューで行い、ポイントアウトキューで値

を更新する.

SPFAアルゴリズム(BFS)テンプレートは以下の通りである:

void spfa_bfs(int st)
{
    memset(dis,60,sizeof(dis));
    memset(bz,false,sizeof(bz));
    int l=0,r=1;
    dis[que[1]=st]=0;
    while(lint now=que[++l];
        bz[now]=false;
        for(int i=first[now];i;i=next[i])
            if(dis[now]+w[i]now]+w[i];
                if(!bz[en[i]]) bz[que[++r]=en[i]]=true;
            }
    }
    return false;
}

注記:que[]はキュー、dis[]はポイントからソースポイントまでの距離、l、rはそれぞれ左右のポインタ、bz[]はフラグ->ポイントがエンキューされているかどうかを示します.

SPFAアルゴリズム(DFS)テンプレートは以下の通りである:

void spfa_dfs(int x)
{
    bz[x]=true;
    for(int i=first[x];i;i=next[i])
        if(dis[now]+w[i]now]+w[i];
            if(!bz[en[i]]]) spfa(en[i]);
        }
    bz[x]=false;
}  

マイナスループ

SPFAアルゴリズムのもう一つの大きな利点は、負のループ

を判定できることである.

SPFAアルゴリズムを用いて負ループを判断するには2つの方法がある.

SPFAアルゴリズムのdfs形式は,1つの経路上に1つの点が複数回現れることを判断する.

SPFAアルゴリズムのbfs形式は,合計頂点数より一点のエンキュー回数が大きいことが判断条件である.

まとめ

SPFAアルゴリズムは効率が高く、実用性が高く、有用なアルゴリズムです!