무방향, 가중 그래프가 주어지고 특정 노드에서 다른 특정 노드까지 가능한 최소 이동 비용이 있는 경로를 찾으라는 요청을 받았다고 가정합니다. 이동 비용은 다음과 같이 계산됩니다. 정점 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 사이에는 두 개의 경로가 있습니다. 최적 경로는 1->2->4이고 경로 비용은 10 + (15 - 10) =15입니다. 그렇지 않으면 경로 비용은 20입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- adjList :=빈 목록이 포함된 새 지도
- 가장자리의 각 항목에 대해 다음을 수행합니다.
- u :=항목[0]
- v :=항목[1]
- w :=항목[2]
- adjList[u] 끝에 쌍(w,v) 삽입
- adjList[v] 끝에 쌍(w,u) 삽입
- q :=새 힙
- v_list :=새로운 세트
- q 끝에 (0,1) 삽입
- 플래그 :=참
- q가 비어 있지 않은 동안 do
- c :=q에서 가장 작은 항목 팝
- v_list에 c[1]이 있으면
- 다음 반복으로 이동
- v_list에 추가(c[1])
- c[1]이 n과 같으면
- 플래그 :=거짓
- c[0]을 반환
- adjList[c[1]]의 각 u에 대해 다음을 수행합니다.
- u[1]이 v_list에 없으면
- out :=최대 (u[0], c[0] ,u[1])
- 힙 q로 푸시
- u[1]이 v_list에 없으면
- 플래그가 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