#1 최단거리 알고리즘 - Dijkstra's Algorithm

 정점들과 그 사이를 연결하는 간선들이 주어졌을 때, 간선의 가중치가 모두 같다면 BFS(깊이우선탐색)를 활용하여 각 정점간의 최단거리를 구할 수 있다.  이번에는 간선들의 가중치가 서로 다를 때 최단거리를 구하기 위해 사용 가능한 알고리즘 중 하나인 Dijkstra의 알고리즘에 대해 정리해본다

 

 

 Dijkstra 알고리즘은 동적 계획법을 활용하여 최단경로를 구하는 알고리즘이다.  절차는 다음과 같다

 

① 먼저 시작점 s로부터의 각 정점까지의 거리를 나타낼 배열 d를 INF(무한)으로 초기화한다.

② d[s]를 0으로 초기화한다 (자기 자신과의 거리는 0이기 때문에)

③ 현 시점에서 가장 s로부터의 거리가 가까운 정점을 경유할 정점 m으로 잡고

    그 점을 경유한 최단거리로 d를 갱신한다. ( s -> m -> i == min(d[i], d[m] + graph[m][i]) )

④ ③을 더이상 갱신이 일어나지 않을 때 까지 반복한다.

 

실제 구현에 있어 주의해야할 부분은 두 가지가 있다. 그래프의 관리방식과 단계③에서 가장 가까운 경유점을 찾는 방식이다. 

 

그래프의 경우 단순히 n * n 배열로 관리하게될 경우 인접 정점을 찾기위해 매번 n-1회의 탐색이 필요하다(O(n)) 이를 해결하려면 그래프를 각 정점의 인접 정점들의 집합을 요소로 가지도록 하면 된다.

INF = float('inf')
g1 = [
    [0, 1, INF, 1],
    [1, 0, 1, INF],
    [INF, 1, 0, 1],
    [1, INF, 1, 0]
]

g2 = [
    [1, 3],
    [0, 2],
    [1, 3],
    [0, 2]
]

g1과 같이 그래프는 관리하는것 보다 g2와 같이 관리할 경우에 인접한 정점을 참조하기 위해 반복문을 보다 적게 돌릴 수 있다.

 

가까운 경유점을 찾는 방법의 경우 단순히 인접한 정점의 갯수만큼 반복문을 돌려 구할 수도 있지만

보다 빠르게 구하고자 한다면 경유할 점과 그 점까지의 거리를 우선순위 큐(힙)에 넣어 관리하면 시간복잡도를 O(logn)까지 줄일 수 있다. 큐에 들어있지만 이미 최단거리가 갱신돼버린 케이스의 존재를 감안해도 상당한 성능 향상을 기대할 수 있다. 

 

위 두가지 요소를 적용한 코드는 아래와 같다.

import sys
import heapq

input = sys.stdin.readline
INF = float('inf')


# 1753 최단경로
# 주어진 정점에서 시작하여 각 정점으로의 최단거리를 구하는 문제
# 다익스트라 알고리즘을 활용하여 해결 가능하다
def sol1753():
    # 정점의 갯수와 간선의 갯수
    v, e = map(int, input().split())

    # 시작점
    s = int(input())

    # 각 정점의 인접 정점과 그 사이의 거리
    g = [[] for _ in range(v + 1)]
    for _ in range(e):
        v1, v2, d = map(int, input().split())
        g[v1].append((v2, d))

    # 처음에는 모든 정점까지의 거리를 무한으로 초기화(자기 자신과의 거리는 0)
    dp = [INF] * (v + 1)
    dp[s] = 0

    # 경유하는 점의 시작으로 자기 자신을 집어넣음
    # 경유할 수 있는 점 중 가장 거리가 짧은 것을 우선적으로 방문하기 위해 우선순위 큐(heapq)를 사용한다
    q = [(0, s)]
    while q:
        distance, vertex = heapq.heappop(q)
        # 만약 경유할 정점까지의 거리가 최단거리가 아닐 경우 스킵
        if dp[vertex] < distance:
            continue
        # 시작점부터 경유할 정점까지의 거리 + 경유할 정점의 인접 정점까지의 거리로 시작점부터 인접 정점까지의 거리를 갱신
        # 갱신된 경우 해당 정점과 그 정점까지의 거리를 큐에 삽입
        for e, d in g[vertex]:
            c = dp[vertex] + d
            if c < dp[e]:
                dp[e] = c
                # 우선순위 기준을 거리로 잡기 위해 (거리, 정점번호) 의 형태로 큐에 삽입
                heapq.heappush(q, (c, e))
    print('\n'.join(map(conv, dp[1:])))


def conv(num):
    return 'INF' if num == INF else str(num)


if __name__ == '__main__':
	sol1753()

백준 온라인저지(Baekjoon Online Judge)의 1753번 문제(https://www.acmicpc.net/problem/1753)에 제출한 코드이다