[APS] 18. Dijkstra(다익스트라) 파이썬(Python)으로 구현하기

1. 다익스트라 알고리즘이란 무엇인가?

---

• MST 다음에 배워서 MST와 비슷한가? 싶었지만 약간 다른 다익스트라!

• MST는 모든 정점을 잇는 간선이 하나씩 존재해서 모든 정점을 다 이었다면, 다익스트라는 시작정점에서 끝정점으로 가는 경로 중에 가중치가 제일 적은 값을 고르는 알고리즘이다!

• 이 때 특징은 ‘유향’ 그래프, 즉 A → B로는 갈 수 있지만 반대로 B → A로는 가지 않는 ‘방향’ 이 주어지는 그래프라는 것이다.

2. 다익스트라 알고리즘 python 으로 구현하기

---

1. V개의 노드를 방문할 때마다 V개의 인접 노드에 대해서 검사하는 방식

→ Prim 알고리즘과 유사한 방식, 시간복잡도가 O(V^2)로 큰편이다.

T = int(input())
for tc in range(1, T+1):
    N, E = map(int, input().split())
    adj = [[] for _ in range(N+1) ]
    for _ in range(E):
        s,e,w = map(int, input().split())
        adj[s].append((e,w))

    D = [11]*(N+1) # 최종가중치가 저장될 리스트
    D[0] = 0

    U = [] # 방문처리를 할 리스트

    for _ in range(N):
        u = 0
        minV = 11
        for i in range(N+1):
            if D[i] < minV and i not in U:
                u = i
                minV = D[u]

        U.append(u)

        for j in range(len(adj[u])):
            D[adj[u][j][0]] = min(D[adj[u][j][0]], minV+adj[u][j][1]) # 끝지점

    print(f"#{tc} {D[N]}")

2. 우선순위 큐 / 최소힙을 이용해서 구현하는 방식

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

            if distance[cur] < dist:
                continue

            for next in adj[cur]:
                cost = dist + next[1]
                if cost < distance[next[0]]:
                    distance[next[0]] = cost
                    heapq.heappush(q, (cost, next[0]))

Uploaded by N2T