JavaScriptで学ぶワーシャル・フロイド法（全点対最短経路アルゴリズム）

全点対最短経路問題とは

ダイクストラ法（Dijkstra's algorithm）は、ある1つのノードから他のすべてのノードへの最短距離・経路を求めるためのアルゴリズムです。しかし、実務では「すべてのノードから、それ以外のすべてのノードへの最短経路」をまとめて求めたいケースがあります。こうした問題に活躍するのが全点対最短経路（All Pairs Shortest Path）アルゴリズムであり、その中で最も広く利用されているのがワーシャル・フロイド法（Floyd-Warshall algorithm）です。

ワーシャル・フロイド法の仕組み

ワーシャル・フロイド法は、以下の手順で動作します。

• N × N の距離行列を無限大（Infinity）で初期化します。
• 各辺 u, v について、行列にその辺の重みを設定します。また、自分自身への辺 v, v については距離を 0 に設定します。
• i、j、k を反復子とする3重のループを作成します。各ノード i から各ノード j への距離に対して、「ノード k を経由したほうが近回線になるか」を検討し、既存の arr[i][j] より小さい値が見つかれば距離を更新します。

なお、ここでは行列の代わりにオブジェクトを使用します。複雑なオブジェクトで各ノードを表現する場合でも、インデックスを意識せずに扱えるためです。

計算量は O(n³) となるため、グラフが大規模になる場合は注意が必要ですが、小〜中規模のグラフなら非常にシンプルかつ効果的な手法です。

それでは、実際の実装を見ていきましょう。

実装例

floydWarshallAlgorithm() {
    let dist = {};
    for (let i = 0; i < this.nodes.length; i++) {
        dist[this.nodes[i]] = {};
        // 既存の辺にはその重みを距離として設定
        this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
        this.nodes.forEach(n => {
            // その他のノードには無限大を設定
            if (dist[this.nodes[i]][n] == undefined)
            dist[this.nodes[i]][n] = Infinity;
            // 自分自身への距離は0に設定
            if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
        });
    }
    this.nodes.forEach(i => {
        this.nodes.forEach(j => {
            this.nodes.forEach(k => {
                // i → k → j の経由が i → j の直接移動より短いか確認し、
                // 短ければ i → j の値を新しい値で更新する
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            });
        });
    });
    return dist;
}
}

動作確認

次のコードで動作を確認できます。

使用例

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");

g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("D", "C", 3);

console.log(g.floydWarshallAlgorithm());

出力結果

このコードを実行すると、次の出力が得られます。

{
    A: { C: 7, B: 3, D: 4, A: 0 },
    B: { A: 3, B: 0, C: 10, D: 7 },
    C: { A: 7, D: 3, B: 10, C: 0 },
    D: { A: 4, C: 3, B: 7, D: 0 }
}

結果を見ると、たとえば A から C への直接の辺の重みは 100 ですが、D を経由する経路（A → D → C）を使うことで距離 7 に短縮されていることがわかります。このように、ワーシャル・フロイド法はすべてのノード間の最短距離を1度の処理で効率的に求めることができる強力なアルゴリズムです。