最短経路問題における三つのアルゴリズムの実行時間の比較

(1)前書き

辺に重みのある単一始点経路問題として有名なアルゴリズムとしてダイクストラ法とベルマンフォード法がありますが、今回の記事ではもう一つSPFAというアルゴリズムを紹介しつつそれらの速度を比較しようと思います。それぞれのテストケースはPythonで作成し、アルゴリズムの実装にはC++を用いています。

また、この記事の結論が知りたい方は「(10)結果のまとめ」を見てください。

(2)アルゴリズムの説明

前書きの三つのアルゴリズムの簡単な説明を以下に記します。
また、以下では頂点数をV、辺数をEとして計算量などの表記を行います。

①ダイクストラ法

辺の重みが非負のグラフにおける最良優先探索によるアルゴリズムで、訪問済みの頂点集合と繋がる頂点のうち最も近い頂点を順に選ぶアルゴリズムになります。また、最も近い頂点の候補を優先度付きキューに保存しておくと$O(\log{V})$で探すことができ、**全体の計算量は$O((E+V)\log{V})$**となります。

②ベルマンフォード法

最短経路が存在する時にその経路にそれぞれの点は一度しか選ばれないことを利用したアルゴリズムです。すなわち、全ての辺を緩める(各頂点の始点からの最短距離と思われる距離に置き換える)ことをV-1回繰り返して最短距離をグラフ全体に伝播させていくアルゴリズムでその**全体の計算量は$O(VE)$**になります。

また、ダイクストラ法と異なり辺の重みが負の場合でも用いることができますが、負閉路がある場合は最短経路が存在しない場合があることに注意が必要です。負閉路の存在はV回目の緩和を全ての辺に対して行った際に最短経路が更新されるものが存在するかによって判定することができます。ただし、今回の実験では負閉路の判定はしません。

③SPFA

ベルマンフォード法を改善したアルゴリズムです。ベルマンフォード法の緩和の際には未訪問の頂点や最短距離が既に確定した頂点から伸びる辺も緩和しますが、緩和できる可能性のある頂点のみを考えることで効率化をします。したがって、頂点の最短距離の更新回数の少ない疎なグラフの場合はベルマンフォード法よりも高速に動作しますが、ベルマンフォードと比べ実装が複雑なので密なグラフの場合はあまり実行時間は変わりません。 また、ベルマンフォード法と同様に辺の重みが負の場合でも用いることができ、**全体の計算量はベルマンフォード法と同様の$O(VE)$**です。

(3)グラフのテストケースの作成

ここでは比較のために全てのテストケースは同じ頂点数$V=2^{10}$とし、疎なグラフと密なグラフの間での実行時間を比較するために辺数が$V \times {2^i} (0 \leqq i <10)$となるグラフを一つずつランダムに生成します。このグラフに多重辺は存在せずそれぞれの辺の重みは$0$以上$2^{10}$以下となります。

from random import sample,randint
n=1024
edges=[(i,j) for i in range(n) for j in range(n) if i!=j]
for i in range(10):
    path=f"{i}.txt"
    seedge=sample(edges,n*(2**i))
    with open(path,mode="w") as f:
        f.write(f"{n} {n*(2**i)}\n")
        for e in seedge:
            f.write(f"{e[0]} {e[1]} {randint(0,n)}\n")

(4)実装したプログラム

実験を行うために三つのアルゴリズムを以下のように実装します。自分なりにできるだけ高速化しましたが、まだ改善の余地があるかもしれません。

また、#include<bits/stdc++.h>で標準ライブラリを全てインクルードし、無限大の値としてINF$(=10^{12})$を用いています。そして、実行速度を測定するために分解能の高いchronoライブラリを用いています。

①ダイクストラ法

#include<bits/stdc++.h>
using namespace std;
using namespace chrono;
typedef long long ll;
#define INF 1000000000000
vector<ll> dist;
vector<vector<vector<ll>>> edges;

void dijkstra(ll n,ll f){
    priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>> q;
    q.push({0,f});
    while(!q.empty()){
        vector<ll> next=q.top();q.pop();
        if(dist[next[1]]<=next[0]) continue;
        dist[next[1]]=next[0];
        for(const auto& edge:edges[next[1]]){
            if(dist[edge[0]]<=next[0]+edge[1]) continue;
            q.push({next[0]+edge[1],edge[0]});
        }
    }
}

signed main(int args, char *argv[]){
    ifstream ifs(argv[1]);
    ll n,m;ifs>>n>>m;
    dist.resize(n);
    for(ll i=0;i<n;i++)dist[i]=INF;
    edges.resize(n);
    for(ll i=0;i<m;i++){
        ll a,b,c;ifs>>a>>b>>c;
        edges[a].push_back({b,c});
    }
    system_clock::time_point t1,t2;
    t1=system_clock::now();dijkstra(n,0);t2=system_clock::now();
    cout<<duration_cast<milliseconds>(t2-t1).count()<<endl;
}

②ベルマンフォード法

#include<bits/stdc++.h>
using namespace std;
using namespace chrono;
typedef long long ll;
#define INF 1000000000000
vector<ll> dist;
vector<vector<vector<ll>>> edges;

void bellmanford(ll n){
    for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
            if(dist[j]!=INF){
                for(const auto& edge:edges[j]){
                    ll new_dist=dist[j]+edge[1];
                    if(dist[edge[0]]>new_dist)dist[edge[0]]=new_dist;
                }
            }
}

signed main(int args, char *argv[]){
    ifstream ifs(argv[1]);
    ll n,m;ifs>>n>>m;
    dist.resize(n);dist[0]=0;
    for(ll i=1;i<n;i++)dist[i]=INF;
    edges.resize(n);
    for(ll i=0;i<m;i++){
        ll a,b,c;ifs>>a>>b>>c;
        edges[a].push_back({b,c});
    }
    system_clock::time_point t1,t2;
    t1=system_clock::now();bellmanford(n);t2=system_clock::now();
    cout<<duration_cast<milliseconds>(t2-t1).count()<<endl;
}

③SPFA

#include<bits/stdc++.h>
using namespace std;
using namespace chrono;
typedef long long ll;
#define INF 1000000000000
vector<ll> dist;
vector<vector<vector<ll>>> edges;

void spfa(ll n,ll s){
    deque<ll> q;
    vector<bool> inq(n);
    vector<ll> co(n); 
    q.push_back(s);
    inq[s]=0;
    ++co[s];
    while(!q.empty()){
        ll now=q.front();
        inq[now]=false;
        for(const auto& edge:edges[now]){
            ll new_dist=dist[now]+edge[1];
            if(dist[edge[0]]>new_dist){
                dist[edge[0]]=new_dist;
                if(!inq[edge[0]] and co[edge[0]]!=n-1){
                    q.push_back(edge[0]);
                    inq[edge[0]]=true;
                    ++co[edge[0]];
                }
            }
        }
        q.pop_front();
    }
}

signed main(int args, char *argv[]){
    ifstream ifs(argv[1]);
    ll n,m;ifs>>n>>m;
    dist.resize(n);dist[0]=0;
    for(ll i=1;i<n;i++)dist[i]=INF;
    edges.resize(n);
    for(ll i=0;i<m;i++){
        ll a,b,c;ifs>>a>>b>>c;
        edges[a].push_back({b,c});
    }
    system_clock::time_point t1,t2;
    t1=system_clock::now();spfa(n,0);t2=system_clock::now();
    cout<<duration_cast<milliseconds>(t2-t1).count()<<endl;
}

(5)プログラムの実行

生成したテストケースのテキストファイルを引数に与える実行を繰り返すために、以下のコードを用いてPythonからC++の実行ファイルを動かしました。

from subprocess import call
for i in ["spfa","dijkstra","bellmanford"]:
    for j in range(10):
        call([f"./{i}",f"{j}.txt"])

(6)実験の結果

実行時間を計測すると以下のようになりました。それぞれのテストケースでそれぞれのアルゴリズムを三回ずつ実行し、外れ値が観測されなかったことから実行結果の平均を記しています。また、時間の単位は[ms]で、1番左の列は辺の本数を表します。

	ダイクストラ法	ベルマンフォード法	SPFA
$2^{10}$本	0	2.6	0
$2^{11}$本	2	63	0
$2^{12}$本	6	115.7	0
$2^{13}$本	15	209.3	0.7
$2^{14}$本	32.7	393	1
$2^{15}$本	67.3	784.7	2.7
$2^{16}$本	140.7	1628.3	5.3
$2^{17}$本	313.7	3959.7	12
$2^{18}$本	685.3	11508	34.6
$2^{19}$本	1555.7	30341.3	107.3

(7)実験の考察

✳︎以下で出てくる問題は全て競技プログラミングのサイトのAtCoderのもので、実行時間は複数のテストケースのうち最大のものです。

計算量に従えば実行速度はダイクストラ法>>SPFA>ベルマンフォード法になると予測していましたが、いずれの辺の本数の場合もSPFA>ダイクストラ法>ベルマンフォード法という結果になりました。また、辺に偏りがないか不安でこちらの問題でもダイクストラ法とSPFAの実行速度を比較しましたが、前者が162ms¹で後者が151ms²となりこの場合もSPFAがダイクストラ法に勝る結果となりました。

したがって、多くのグラフではSPFAがダイクストラ法に勝ると結論づけました。また、頂点数が増えるほど計算量的にダイクストラ法が有利なので、さらに頂点数を増やすとダイクストラ法とSPFAの速度に逆転が見られるのではないかと予想しています³。

さらに、辺の本数が$2^{14}$の時はSPFAがダイクストラ法より30倍程度速いのに対し、辺の本数が$2^{19}$の時はSPFAがダイクストラ法より15倍程度速いので、SPFAがより疎なグラフほど高速であるということも示されています。

ただし、こちらの問題でベルマンフォード法とSPFAの実行時間を比較しましたが、前者が131ms⁴で後者が185ms⁵で今度はベルマンフォード法がSPFAに勝る結果となりました。しかし、テストケースを解析したところ、密なグラフではベルマンフォード法が勝り、疎なグラフではSPFAが勝っていました。そこで、これを以下の追加実験で確かめることにしました。

(8)追加実験の結果

(7)の最後の考察より、辺の重みが$-2^{10}$以上$2^{10}$以下をとる場合についての追加実験を行いました。⁶
また、以下の表では、()内に辺の重みが非負の場合でのそのアルゴリズムの実行時間を記しています。

	ベルマンフォード法	SPFA
$2^{10}$本	2.6(2.6)	0(0)
$2^{11}$本	80.7(63)	201.3(0)
$2^{12}$本	155.3(115.7)	327(0)
$2^{13}$本	288.7(209.3)	476.3(0.7)
$2^{14}$本	586.7(393)	765(1)
$2^{15}$本	1185.3(784.7)	1396.7(2.7)
$2^{16}$本	2526(1628.3)	2650.7(5.3)
$2^{17}$本	6303.7(3959.7)	6264.3(12)
$2^{18}$本	16439(11508)	18469(34.6)
$2^{19}$本	35944.7(30341.3)	44101(107.3)

(9)追加実験の考察

この表を見ると、辺の重みが非負の場合と比べてベルマンフォード法は最大でも1.6倍程度しか実行速度が遅くなっていません。それに対し、SPFAでは辺の重みが非負の場合と比べると最大で700倍程度まで実行速度が遅くなっています。

したがって、辺の重みが非負の時と比べると辺の重みが負の辺を含む時は最短距離を更新する回数が多いためSPFAの実行速度は遅くなり、ベルマンフォード法は負の辺を含むかどうかに関わらず毎回全ての辺について緩和を行うので実行速度はほとんど変わらないと結論づけることができます。⁷

また、ベルマンフォード法は辺の本数が$2^{10}$本の場合を除いた全ての場合でSPFAに実行速度で勝っています。したがって、ある程度密で負の辺を含むグラフの場合はベルマンフォード法の方がより高速に動作することもここから言うことができそうです。

#(10)結果のまとめ

グラフの辺の重みが非負の場合
$\rightarrow$実行速度はSPFA>ダイクストラ法>ベルマンフォード法
　ただし、頂点数が増えると、(おそらく)SPFA<ダイクストラ法

グラフ辺の重みが負も含む場合
$\rightarrow$実行速度はベルマンフォード法>SPFA
　ただし、グラフが十分に疎である場合、ベルマンフォード法<SPFA

#(11)後書き

今回の記事は大学のレポートをQiita用に書き直したものです。自分の予想に反した結果が得られたのですが、アルゴリズム的には至極真っ当な結果だと思うので、面白いなと思いました。
定期的にこのような実行速度の比較のような実験系の記事も書いていきたいと思っています。

(追記)
テストケースなど含む今回使用したコードは全てgithubに上げてあります。

1. 自分の提出へのリンク ↩

2. 自分の提出へのリンク ↩

3. 実行時間を考慮して今回は頂点数を$2^{10}$に制限しました ↩

4. 自分の提出へのリンク ↩

5. 自分の提出へのリンク ↩

6. 「(3)グラフのテストケースの作成」における辺の重みを変えれば良いだけです。 ↩

7. 実装の複雑さのぶんだけSPFAの方が遅いとも言えそうです。 ↩