Python의 가중 그래프에서 가능한 최소 비용을 찾는 프로그램

<시간/>

무방향 그래프를 나타내는 edge라고 하는 정수의 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]
- 가중치[u, v] :=w
- 가중치[v, u] :=w
- N :=N의 최대값, u + 1, v + 1
- max_weight :=max_weight의 최대값, w
결과 :=무한대
max_weight>=0인 동안 수행
- d, weight :=bfs(0, max_weight)
- d>=0이면
  - 결과 :=결과의 최소값, d * 가중치
  - max_weight :=무게 - 1
- 그렇지 않으면
  - 루프 종료
결과가 <무한대이면 -1
이면 결과를 반환합니다.
bfs() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다. weight_cap
- 대상 :=N - 1
- Q :=root, 0, 0을 포함하는 데크
- 방문 :=[거짓] * N
- 방문[0] :=사실
- Q가 비어 있지 않은 동안 수행
  - v, d, current_weight :=Q에서 마지막 요소 삭제
  - v가 N - 1과 같으면
    - 리턴 d, current_weight
  - 그래프[v]의 각 w에 대해 수행
    - 방문[w]이 0이 아니면
      - 다음 반복을 계속하십시오
    - new_weight :=가중치[v, w]
    - new_weight <=weight_cap이면
      - 방문[w] :=참
      - 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]
]

Python의 가중 그래프에서 가능한 최소 비용을 찾는 프로그램

예시

입력

출력