220307 - 최단 거리

◾ 최단 경로 : 백준 1753번

• https://www.acmicpc.net/problem/1753

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

---

입력

• 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다.
• 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다.
• 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

• 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

입출력 예

Input	Output
5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6	0 2 3 7 INF

---

◾ 풀이

1. 해설

• 다익스트라 알고리즘을 사용하여 해결할 수 있다.
• 시작점을 기준으로 각 정점으로 가는 최단 거리를 찾는다.

---

2. 프로그램

1. v, e, k 입력
2. edges 입력
3. result 초기화
4. heap을 통해 각 정점을 통해 가는 거리 확인
   • 최단거리일 경우 result 변경
5. result 출력
   • 1e6인 경우 INF 출력
   • 1e6이 아닌 경우 해당 값 출력

# 코드
import heapq

# 시간 초과 해결을 위해 사용
# import sys
# input = sys.stdin.readline

v, e = map(int, input().split(' '))
k = int(input())

edges = {i : [] for i in range(1, v+1)}
for _ in range(e):
    v1, v2, w = map(int, input().split(' '))
    edges[v1].append((v2, w))

result = [1e6] * (v + 1)
result[k] = 0
heap_data = []
heapq.heappush(heap_data, (0, k))
while heap_data:
    w_, v_ = heapq.heappop(heap_data)
    if result[v_] < w_:
        continue
    for i in edges[v_]:
        cost = w_ + i[1]
        if result[i[0]] > cost:
            result[i[0]] = cost
            heapq.heappush(heap_data, (cost, i[0]))

for w_ in result[1:]:
    if w_ == 1e6:
        print("INF")
    else:
        print(w_)

• Input
  5 6
  1
  5 1 1
  1 2 2
  1 3 3
  2 3 4
  2 4 5
  3 4 6