JavaScriptで実装するダイクストラ法：重み付きグラフの最短経路を求めるアルゴリズム

ダイクストラ法（Dijkstra's algorithm）は、重み付きグラフにおけるノード間の最短経路を求めるための代表的なアルゴリズムです。グラフを作成する際に addEdge や addDirectedEdge のメソッドを使えば、エッジに重みを設定できます。ここでは、このアルゴリズムがどのように動作するのかを順番に見ていきましょう。

ダイクストラ法の基本的な流れ

• 距離を格納するコレクションを作成し、始点ノード以外のすべての頂点の距離を無限大（Infinity）に設定します。
• 始点ノードの距離は 0 なので、優先度 0 として最小優先度キュー（min-priority queue）にエンキューします。
• 優先度キューが空になるまでループ処理を続け、毎回最小距離のノードをキューから取り出します。
• 「現在のノードの距離 ＋ エッジの重み ＜ 次のノードの距離」が成立する場合は、隣接ノードの距離を更新し、新しい距離とともにそのノードをキューへプッシュします。
• 優先度キューが空になるまでこの処理を繰り返します。

このアルゴリズムの基本的な考え方は、「すべてのノードは始点から無限大の距離にある」と仮定して処理を始めるところにあります。その後、エッジを順に評価しながら各ノードの始点からの距離を記録し、途中により低コストの経路が見つかるたびに距離情報を更新していきます。二分ヒープなどの優先度キューを用いた場合、計算量は O((V + E) log V) 程度となり、負の重みを持たないグラフに対して効率的に動作します。

コードによる実装例

djikstraAlgorithm(startNode) {
    let distances = {};

    // 直前のノードへの参照を保持
    let prev = {};
    let pq = new PriorityQueue(this.nodes.length * this.nodes.length);

    // 始点以外のすべてのノードの距離を無限大に設定
    distances[startNode] = 0;
    pq.enqueue(startNode, 0);
    this.nodes.forEach(node => {
        if (node !== startNode) distances[node] = Infinity;
        prev[node] = null;
    });

    while (!pq.isEmpty()) {
        let minNode = pq.dequeue();
        let currNode = minNode.data;
        let weight = minNode.priority;
        this.edges[currNode].forEach(neighbor => {
            let alt = distances[currNode] + neighbor.weight;
            if (alt < distances[neighbor.node]) {
                distances[neighbor.node] = alt;
                prev[neighbor.node] = currNode;
                pq.enqueue(neighbor.node, distances[neighbor.node]);
            }
        });
    }
    return distances;
}

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

実行例

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

g.addDirectedEdge("A", "C", 100);
g.addDirectedEdge("A", "B", 3);
g.addDirectedEdge("A", "D", 4);
g.addDirectedEdge("D", "C", 3);
g.addDirectedEdge("D", "E", 8);
g.addDirectedEdge("E", "F", 10);
g.addDirectedEdge("B", "G", 9);
g.addDirectedEdge("E", "G", 50);

console.log(g.djikstraAlgorithm("A"));

出力結果

上記のコードを実行すると、以下の出力が得られます。

{ A: 0, B: 3, C: 7, D: 4, E: 12, F: 22, G: 12 }

この結果から、たとえばノード A からノード C への最短距離は 7 であることがわかります。A → C を直接結ぶエッジの重みは 100 ですが、A → D → C という経路を通れば 4 ＋ 3 ＝ 7 というはるかに低いコストで到達できるためです。このように、ダイクストラ法は一見遠回りに見える経路の中から、実際には最もコストの低い経路を見つけ出すことができます。