【Python】最小の頂点から最大の頂点までの最小コスト経路を求めるアルゴリズム

問題の概要

重み付き無向グラフが与えられ、あるノードから別のノードへ移動するときのコストが最小となる経路を見つけることを考えます。移動コストは次のように計算されます。たとえば、頂点Aから頂点Cへ向かう経路が A → B → C であるとき、AからBへの移動コストが10、BからCへの移動コストが20だとします。このとき、AからCまでの合計コストは「AからBまでの移動コスト」に「BからCへの移動コストと、Bまでに累積したコストとの差」を加えたものになります。つまり、10 + (20 − 10) = 20 となります。

求めるのは、グラフ内で最も小さい番号を持つノード（頂点1）から、最も大きい番号を持つノード（頂点n）までの最小の移動コストです。

入力例と出力

たとえば、入力として次のようなグラフが与えられたとします。

このとき、出力は 15 になります。

頂点1と頂点4の間には2つの経路が存在します。最適な経路は 1 → 2 → 4 であり、そのコストは 10 + (15 − 10) = 15 です。一方、頂点1と4を直接結ぶ経路を選ぶと、コストは20かかってしまいます。

解き方のアプローチ

この問題は、ダイクストラ法を応用して解くことができます。ポイントは、累積コストを「それまでに通過した辺の重みの最大値」として更新していく点です。これにより、全体のコストを最小化する経路を効率よく見つけられます。具体的な手順は以下の通りです。

• adjList := 空のリストを値に持つ新しいマップ（隣接リスト）を作成する
• edges 内の各要素について、次を実行する
  • u := item[0]
  • v := item[1]
  • w := item[2]
  • adjList[u] の末尾にペア (w, v) を挿入する
  • adjList[v] の末尾にペア (w, u) を挿入する
• q := 新しいヒープを作成する
• v_list := 新しいセットを作成する（訪問済みノードの記録用）
• q の末尾に (0, 1) を挿入する
• flag := True とする
• q が空でない間、次を繰り返す
  • c := q から最小の要素を取り出す
  • c[1] が v_list に既に存在する場合は、次の反復へ進む
  • c[1] を v_list に追加する
  • c[1] が n と等しい場合は、flag := False として c[0] を返す
  • adjList[c[1]] 内の各 u について、u[1] が v_list に存在しなければ、out := (max(u[0], c[0]), u[1]) を計算し、out をヒープ q にプッシュする
• flag が True のままであれば、-1 を返す（頂点nに到達できないケース）

実装例

理解を深めるために、以下のPython実装を見てみましょう。

from collections import defaultdict
import heapq

def solve(n, edges):
    adjList = defaultdict(list)
    for item in edges:
        u, v, w = map(int, item)
        adjList[u].append((w, v))
        adjList[v].append((w, u))

    q = []
    v_list = set()
    q.append((0, 1))
    flag = True

    while q:
        c = heapq.heappop(q)
        if c[1] in v_list:
            continue
        v_list.add(c[1])
        if c[1] == n:
            flag = False
            return c[0]
        for u in adjList[c[1]]:
            if u[1] not in v_list:
                out = (max(u[0], c[0]), u[1])
                heapq.heappush(q, out)

    if flag:
        return -1

print(solve(4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)]))

入力

4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)]

出力

15

計算量について

このアルゴリズムでは、各ノードを高々一度ずつ確定し、各辺に対してヒープへの挿入が最大1回行われます。二分ヒープを使用する場合、時間計算量は O((V + E) log V) 程度となり、大規模なグラフでも効率的に動作します。

このように、優先度付きキュー（ヒープ）を活用することで、頂点1から頂点nまでの最小コスト経路を簡潔かつ高速に求めることができます。