JavaScriptで実装する最短経路アルゴリズム ― 重み付きエッジの追加方法

グラフ理論における最短経路問題とは、グラフ上の2つの頂点（ノード）をつなぐ経路の中から、構成するエッジ（辺）の重みの合計が最小となるものを見つける問題です。このアルゴリズムを実装するためには、既存のaddEdgeメソッドとaddDirectedEdgeメソッドを修正し、エッジに重みを設定できるように拡張する必要があります。

重み付きエッジを追加する実装例

それでは、実際にどのように重みを扱えるようにするのか、コードを見ていきましょう。

/**
 * 同じ重みを持つ双方向のエッジを追加します
 *
 *            weight
 * node1 <================> node2
 *            weight
 *
 */
addEdge(node1, node2, weight = 1) {
    this.edges[node1].push({ node: node2, weight: weight });
    this.edges[node2].push({ node: node1, weight: weight });
}

/**
 * 次のような一方向のエッジを追加します
 *
 *            weight
 * node1 ----------------> node2
 *
 */
addDirectedEdge(node1, node2, weight = 1) {
    this.edges[node1].push({ node: node2, weight: weight });
}

/**
 * グラフの内容を表示します
 */
display() {
    let graph = "";
    this.nodes.forEach(node => {
        graph += node + "->" + this.edges[node].map(n => n.node).join(", ") + "\n";
    });
    console.log(graph);
}

デフォルト重みのポイント

この実装のポイントは、第3引数のweightにデフォルト値として「1」を設定している点です。これにより、グラフにエッジを追加する際に重みを明示的に指定しなくても、自動的に重み「1」が割り当てられるため、従来の無重みグラフとしてもそのまま利用できます。

つまり、このひとつのデータ構造で無重みグラフと重み付きグラフの両方に対応できる柔軟な設計になっています。これで準備は完了です。次のステップでは、この重み付きグラフを活用して、ダイクストラ法やベルマン・フォード法といった代表的な最短経路アルゴリズムを実装していきます。