Dijkstra - BOK 1753 : 최단 경로

Dijkstra

정의

• 하나의 정점에서 나머지 모든 정점까지의 최단 거리를 찾는 알고리즘 이다.

• 모든 정점의 최단 거리를 구하는 플로이드 워셜 알고리즘과 다른 알고리즘 이다.

예제

출처 : https://www.acmicpc.net/problem/1753

예제의 입력을 그래프로 표현한 것 입니다.

시작점 1에서 다른 정점들 까지의 거리 중 최단거리에 있는 정점을 찾는 문제입니다.

풀이

1. 시작점 1번에서 직접 갈 수 있는 정점은 2번과 3번입니다. 그리고 문제의 조건에서 시작점 자신은 0으로 출력하라고 했으니 고려하여 테이블을 작성해보았습니다.

2. 현재 테이블 기준으로 자기 자신을 제외한 가장 가따운 정점을 선택하여 테이블을 갱신하는 알고리즘을 수행합니다.

2-1. 현재 테이블에서 가장 가까운(가중치가 적은) 정점을 선택합니다. (2번 선택)
2-2. 2-1)번에서 선택한 정점에서 갈 수 있는 정점을 조사합니다.

1. 해당 정점에서 갈 수 있는 경우를 조사합니다.
(2→3의 가중치 : 4 , 2→4의 가중치 : 5에 관한 데이터를 최소 힙에 넣어줍니다.)

2. 최소 힙에서 가장 가중치가 적은 노드를 선택합니다. (2→3의 가중치 : 4 선택)
시작점에서 해당 노드까지의 최소 거리를 확인 후 테이블을 갱신합니다.
(1→3의 가중치 : 3 , 1→2→3의 가중치 : 6(=2+4) 이므로, 현재 테이블을 유지합니다.)

(2→4의 가중치 : 5 선택)
(1→2→4의 가중치 : 7(=2+5)이고 현재 테이블의 값(INF)보다 작기 때문에, 테이블의 값을 7로 업데이트 합니다.)
(이어서 탐색할 필요가 있는 노드라고 판단하여 최소 힙에 넣어 줍니다.)

2-3. 2-1 ~ 2-2의 과정을 최소 힙이 비어질 때까지 반복한다.

코드

import sys
import heapq

input = sys.stdin.readline
INF = sys.maxsize

# 정점의 개수 V, 간선의 개수 E
V, E = map(int, input().split())
# 시작점 K
K = int(input())
# 가중치 테이블
dp = [INF] * (V + 1)
# 최소 힙
heap = []
# 그래프
graph = [[] for _ in range(V + 1)]

# Dijkstra Algorithm
def Dijkstra(start):
    # 가중치 테이블에서 시작 정점에 해당하는 가중치를 0으로 초기화
    dp[start] = 0
    # 최소 힙에 (가중치, 시작 정점)를 넣어줍니다.
    heapq.heappush(heap, (0, start))

    # 최소 힙에 원소가 없을 때 까지 반복
    while heap:
        # 최소 힙에서 가장 가중치가 적은 노드를 선택합니다.
        weight, now = heapq.heappop(heap)

        # 현재 테이블과 비교하여 불필요한(더 가중치가 큰) 튜플이면 무시.
        if dp[now] < weight:
            continue

        # now 가 시작 지점인 모든 간선을 확인합니다.
        for w, next_node in graph[now]:
            # 현재 정점 까지의 최소 가중치 weight + 현재 정점에서 다음 정점(next_node)까지의 가중치 w
            # = 다음 노드까지의 가중치 (next_weight)
            next_weight = weight + w

            # 다음 노드까지의 가중치(next_weight)가 현재 테이블(dp)에 기록된 값 보다 작으면
            if next_weight < dp[next_node]:
                # 계산했던 다음 노드의 가중치(next_weight)로 테이블(dp)을 갱신합니다.
                dp[next_node] = next_weight
                
                # 다음 정점 까지의 가중치와 다음 정점에 대한 정보를 최소 힙에 넣어줍니다.
                heapq.heappush(heap, (next_weight, next_node))

# 초기화
for _ in range(E):
    # u에서 v로 가는 가중치 w인 간선
    u, v, w = map(int, input().split())
    # (가중치, 목적지 노드) 형태로 저장
    graph[u].append((w, v))
    
# Dijkstra Algorithm 수행
Dijkstra(K)

# 출력
for i in range(1, V+1):
    if dp[i] == INF:
        print("INF")
    else:
        print(dp[i])

출처 : https://sungmin-joo.tistory.com/33