[백준]1753 (다익스트라 알고리즘)

다익스트라 알고리즘

최단경로를 찾는 알고리즘 중 한개이다.

특정한 한개의 노드에서 나머지 노드의 최단 거리를 찾을 때 사용한다.

다익스트라 알고리즘의 원리는 이와 같다.

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다
3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3, 4를 반복한다.

즉, 다익스트라 알고리즘은 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 찾아 해당노드에서의 다른 노드의 거리를 비교해 갱신하는 것을 반복하는 것이 핵심이다.

그래서 이것을 빠르게 사용하기 위해서는 우선순위 큐를 사용하여 방문하지 않은 노드를 리스트에 삽입 후 사용하면 빠르게 접근할 수 있다.

---

구현

import sys  
input = lambda : sys.stdin.readline()  
import heapq  

V, E = list(map(int, input().split()))  
graph = [[] for _ in range(V)]  

INF = int(1e9)  
ans = [INF for _ in range(V)]  
start = int(input()) - 1  

for _ in range(E):  
    u, v, w = list(map(int, input().split()))  
    graph[u-1].append([v-1, w])  

ans[start] = 0  

q = []  
heapq.heappush(q, (0, start))  
while q:  
    dist, now = heapq.heappop(q)  
    if ans[now] < dist:  
        continue  
    for i, j in graph[now]:  
        cost = dist + j  
        if cost < ans[i]:  
            ans[i] = cost  
            heapq.heappush(q, (cost, i))  

for i in ans:  
    if i == INF:  
        print("INF")  
    else:  
        print(i)

최단경로

참고 : 이것이 코딩테스트다