[알고리즘/Python] (예제) Dijkstra(다익스트라) 알고리즘 (최단경로 구하기) - Shortest Path

 

 

앞서 다익스트라 알고리즘에 대한 개념을 익혀보았으니 최단 거리 구하는 문제들을 몇 가지 살펴보자

 

방식 1. Priority Queue 모듈을 사용

 

BOJ 1753

 

 

import sys
from queue import PriorityQueue

input = sys.stdin.readline

# 노드, 에지 개수
V, E = map(int, input().split())
# 출발 노드
K = int(input())

# 거리 리스트 (노드 갯수보다 한 개 많게 설정(노드 1부터 시작하게끔))
distance = [sys.maxsize] * (V+1)  # 충분히 큰 값으로 초기화
# 방문 여부 저장 리스트
visited = [False] * (V+1)
# 에지 데이터 저장 인접 리스트 (그래프)
myList = [[] for _ in range(V+1)]
# 큐
q = PriorityQueue()


for i in range(E):
    # 인접 리스트에 에지 정보 저장
    # 출발노드, 도착 노드, 가중치
    u, v, w = map(int, input().split())
    myList[u].append((v, w))

    print("gu:", u, myList[u])

# 시작노드 큐에 추가
# 0을 먼저 쓴 이유: 앞에 값 기준으로 자동 정렬되기 때문에(자동으로 거리가 최소인 노드를 선택)
q.put((0, K))
# 시작 노드 값 0으로 설정
distance[K] = 0

# queue 빌 때까지 반복
while q.qsize() > 0:
    # 현재 노드 불러옴
    current = q.get()
    # 현재 노드에서 갈 수 있는 목표 노드 설정
    # 1번 째 인덱스에 k 넣고, 0번째에 가중치를 넣기 때문에 [1]
    c_v = current[1]

    print("cd, cv:", current, c_v)

    if visited[c_v]:
        # 방문한 적 있으면 반복 계속
        continue

    # 현재 노드를 방문한 노드로 업데이트
    visited[c_v] = True

    # 현재 선택 노드에서 나갈 수 있는 에지 가져옴
    # myList[c_v]: 각 n번째 노드와 연결되어 있는 노드와 가중치
    for tmp in myList[c_v]:
        # 다음 노드
        next = tmp[0]
        # 에지의 가중치
        value = tmp[1]

        # if 연결노드 방문 전 and 현재 선택 노드 최단거리 + 비용 < 연결 노드의 최단거리
        if distance[next] > distance[c_v] + value:
            distance[next] = distance[c_v] + value
            # 우선순위 큐에 연결 노드 추가
            # 거리 리스트 기준으로 값 정렬하고 싶기 때문에 distance 먼저 넣음
            q.put((distance[next], next))

for i in range(1, V+1):
    # if distance[i] != sys.maxsize:
    if visited[i]:
        # 해당 거리 노드의 값을 넣어줌
        # i번 노드까지 최단 경로 출력
        print(distance[i])
    else:
        # 방문하지 않았으면 무한대 값 출력(경로 없음)
        print("INF")

 

# 노드, 간선 수
5 6
# 출발 노드
1
# 시작 정점, 도착정점, 가중치(길이)
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6


3

 

다음 입력 예제를 삽입하면 3이 출력된다.

 

 

 

방식2. heap을 사용하는 경우

 

minheap 구조를 사용하여 시간 복잡도를 개선한다.

heapq.heappush(리스트, (거리, 노드)) 로 큐를 설정한다.

모든 노드를 확인하여 최단 거리 노드를 선택하는 것을 최소힙 우선순위 큐를 사용하여 비용 계산의 효율성을 개선.

 

import heapq


def dijkstra(graph, start, final):
    costs = {}
    pq = []
    heapq.heappush(pq, (0, start))

    while pq:
        cur_cost, cur_v = heapq.heappop(pq)
        print("cd, cv:", cur_cost, cur_v)
        # 방문 안했으면 비용 업데이트 수행
        if cur_v not in costs:
            # 비용 업데이트
            costs[cur_v] = cur_cost
            for cost, next_v in graph[cur_v]:
                next_cost = cur_cost + cost
                # heappush하면 알아서 우선순위 가장 높은걸 맨 앞에 넣어줌(정렬)
                heapq.heappush(pq, (next_cost, next_v))

    return costs[final]


graph = {...}
dijkstra(graph, 1, 8)
# 1번 노드에서 8번 노드로 가는 무수히 많은 경로 중 최단경로 구하기