Pythonの加重グラフから可能な最小コストを見つけるためのプログラム

無向グラフの表現であるエッジと呼ばれる整数の2Dリストがあるとします。入力のすべての行はエッジ[u、v、w]を表します。これは、ノードuとvが接続されており、エッジの重みがwであることを意味します。グラフは、0からn-1までのn個のノードで構成されています。

パスのコストは、ここでは、エッジの数とパス内の任意のエッジの最大重みの積として定義されます。ノード0からノードn-1までの可能な最小コストを見つける必要があります。そのようなパスが存在しない場合は、答えを-1と宣言します。

So, if the input is like edges = [
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
], then the output will be 600

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

• グラフ：=新しいマップ

• 重み：=新しいマップ

• max_weight：=0

• N：=0

• エッジのu、v、wごとに、実行します

  • グラフの最後にvを挿入します[u]

  • グラフの最後にuを挿入します[v]

  • weights [u、v]：=w

  • weights [v、u]：=w

  • N：=最大N、u + 1、v + 1

  • max_weight：=max_weightの最大値、w

• 結果：=無限大

• max_weight> =0の場合、実行

  • d、重み：=bfs（0、max_weight）

  • d> =0の場合、

    • 結果：=結果の最小値、d*重み

    • max_weight：=weight-1

  • それ以外の場合

    • ループを終了します

• 結果が<無限大の場合は結果を返し、それ以外の場合は-1

• 関数bfs（）を定義します。これはルートになります、weight_cap

  • ターゲット：=N-1

  • Q：=ルート、0、0を含む両端キュー

  • 訪問した：=[誤り]* N

  • 訪問済み[0]：=True

  • Qが空でない間、実行します

    • v、d、current_weight：=Qから最後の要素を削除

    • vがN-1と同じ場合、

      • d、current_weightを返す

    • グラフ[v]の各wについて、実行

      • visited [w]がゼロ以外の場合、

        • 次の反復を続行します

      • new_weight：=weights [v、w]

      • new_weight <=weight_capの場合、

        • 訪問済み[w]：=True

        • Qの左側に（w、d + 1、最大（current_weight、new_weight））を追加します

  • -1、-1を返す

例

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

from collections import defaultdict, deque
class Solution:
   def solve(self, edges):
      graph = defaultdict(list)
      weights = {}
      max_weight = 0
      N = 0
      for u, v, w in edges:
         graph[u].append(v)
         graph[v].append(u)
         weights[u, v] = w
         weights[v, u] = w
         N = max(N, u + 1, v + 1)
         max_weight = max(max_weight, w)
      def bfs(root, weight_cap):
         target = N - 1
         Q = deque([(root, 0, 0)])
         visited = [False] * N
         visited[0] = True
         while Q:
            v, d, current_weight = Q.pop()
            if v == N - 1:
               return d, current_weight
            for w in graph[v]:
               if visited[w]:
                  continue
               new_weight = weights[v, w]
               if new_weight <= weight_cap:
                  visited[w] = True
                     zQ.appendleft((w, d + 1, max(current_weight, new_weight)))
         return -1, -1
      result = float("inf")
      while max_weight >= 0:
         d, weight = bfs(0, max_weight)
         if d >= 0:
            result = min(result, d * weight)
            max_weight = weight - 1
         else:
            break
      return result if result < float("inf") else -1

ob = Solution()
print (ob.solve( [
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
]))

入力

[
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
]

出力

600