1753 최단경로 그래프

골5

다익스트라 문제였다.

다익스트라는 기본적으로 두 가지 방법으로 풀 수 있는데

첫번째 방법은 O(n^2) 의 시간복잡도가 걸리고, 두번째 방법은 O(nlogn) 의 시간복잡도가 소요된다.

당연히 두번째 방법을 쓰는 게 좋다.

중요한 건 다익스트라 알고리즘의 어떤 부분에서 시간복잡도를 다르게 만들 수 있는지 알고 있는 것이다.

먼저 다익스트라 알고리즘의 전개 과정을 적고 어떤 부분에서 다를 수 있는지 확인한다.

1. 특정 노드(시작노드) 에서 다른 노드로 가는 cost를 모두 무한대로 초기화 한다.
2. graph 배열(인접리스트) 를 만들어서 경로를 모두 배열에 담아준다.
3. start부터 순회를 시작한다
   4. 우선순위큐 or heapq 를 만들어서 방문해야 할 노드들을 담아준다. O(logn)
   4-1. cost 배열을 순회하면서 최소 노드를 찾는다. O(n)
4. cost의 최소 노드를 찾아서 기존에 저장되어있던 경로의 cost와 최소노드를 거쳐가는 cost를 비교해서 더 작은 값을 담아준다.
5. 이렇게 모든 노드를 순회하면 최종적으로 특정노드에서 모든 노드를 가는 최소 cost가 배열에 담기게 된다.

모든 노드를 순회하면서 최소 경로를 찾는 방법과 heap을 이용해 최소 경로를 O(logn)의 시간 복잡도를 통해 찾는 방법이 큰 차이를 만든다.

import heapq

V, E = map(int, input().split(" "))
INF = int(1e9)

start = int(input())
graph = [[] for _ in range(V+1)]
distance = [INF] * (V+1)

for i in range(E):
    a, b, c = map(int, input().split(" "))
    graph[a].append((b, c))

def solution():
    global start
    dijkstra(start)
    for i in range(1, V+1):
        if distance[i] == INF:
            print("INF")
        else:
            print(distance[i])


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
solution()