最小値の頂点から最大値の頂点までの最小コストパスを見つけるプログラム（Python）

無向の重み付きグラフが与えられ、特定のノードから別の特定のノードへの可能な最小の移動コストでパスを見つけるように求められたとします。移動コストは次のように計算されます。頂点Aから頂点Cの間にA->B->Cのパスがあるとします。AからBへの移動コストは10で、BからCへの移動コストは20です。 。AからCへの移動コストは、（AからBへの移動コスト）+（BからCへの移動コストとノードBへの累積移動コストの差）になります。したがって、これは10 +（20-10）=20に変換されます。最初のノードから最後のノード（最小値のノードから最大値のノード）内の可能な最小移動値を見つける必要があります。与えられたグラフ。

したがって、入力が次のような場合

その場合、出力は15になります。

頂点1と4の間に2つのパスがあります。最適なパスは1->2->4で、パスのコストは10 +（15-10）=15です。それ以外の場合、パスのコストは20になります。

これを解決するには、次の手順に従います-

• adjList：=空のリストを含む新しいマップ
• エッジの各アイテムについて、
  • u：=item [0]
  • v：=item [1]
  • w：=item [2]
  • adjList [u]の最後にペア（w、v）を挿入します
  • adjList [v]の最後にペア（w、u）を挿入します
• q：=新しいヒープ
• v_list：=新しいセット
• qの最後に（0,1）を挿入
• フラグ：=True
• qが空でない間は、
  • c：=qから最小のアイテムをポップ
  • c [1]がv_listに存在する場合、
    • 次の反復に進む
  • v_listに（c [1]）を追加
  • c [1]がnと同じ場合、
    • フラグ：=False
    • return c [0]
  • adjList [c [1]]の各uについて、
    • u [1]がv_listに存在しない場合、
      • out：=最大（u [0]、c [0]、u [1]）
      • ヒープにプッシュするq
• フラグがTrueの場合、
  • 戻り値-1

例

理解を深めるために、次の実装を見てみましょう-

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