악곱 == 악성곱슬

다익스트라

---

다익스트라 복습하기 위해서 기본 문제를 풀어보았다. 도시의 개수(노드)는 최대 1000개, 버스의 개수(간선) 10만이다.

다익스트라는 2가지 방법으로 구현할 수 있었다. 시간복잡도가 둘이 다르다. 각각 O(V^2), O(ElogV)이다. 여기서는 노드의 개수가 1000개밖에 되지 않아 무엇을 사용해도 무방하나, 거의 대부분 후자가 빠를 가능성이 농후하기 때문에 후자로 구현해보았다.

다익스트라는 그리디하게 최소 비용을 업데이트 하는 알고리즘이다. 최단경로 optimal substructure에 의해 이미 최단경로라면, 다른 어떤 경로로 돌아와도 최단경로를 만들 수 없다는 이론에 의해 증명된다.

따라서 우선순위큐를 사용하여 가장 최단거리 노드를 하나씩 업데이트 해가며 single - all 의 최단경로를 구할 수 있다.

복습 끝-

구현

---

import sys
import heapq

def dijkstra(start, dest, n):
    dist = [INF] * (n+1)
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    while heap:
        cost, node = heapq.heappop(heap)
        if cost > dist[node]:
            continue
        for to, length in adj_lst[node]:
            if dist[node] + length < dist[to]:
                dist[to] = dist[node] + length
                heapq.heappush(heap, (dist[to], to))
    return dist[dest]

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    M = int(sys.stdin.readline().rstrip())
    adj_lst = [[] for _ in range(N+1)]
    INF = int(1e9)
    for _ in range(M):
        _start, _end, _cost = map(int, sys.stdin.readline().rstrip().split())
        adj_lst[_start].append([_end, _cost])
    S, D = map(int, sys.stdin.readline().rstrip().split())
    print(dijkstra(S, D, N))