다익스트라 알고리즘

설명

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 입니다. 다익스트라 알고리즘은 그리디 알고리즘으로 분류가 됩니다. 그 이유는 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문입니다.

원리

1. 출발 노드를 설정합니다.
2. 최단 거리 테이블을 초기화합니다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.
5. 위 과정에서 3번과 4번을 반복합니다.

즉, 매번 최단 거리를 선택해서 진행을 하면 된다.

** 최단 거리 테이블 : 출발 노드에 대해서 각 노드에 도달하는데 걸리는 최단 거리 정보를 저장하는 테이블. 1차원 리스트로 관리한다.

우선순위 큐

다익스트라는 항상 거리가 짧은 간선을 선택하는 알고리즘이다. 우선순위 큐는 항상 가치가 높은 물건 데이터를 꺼낼 수 있다. 즉 여기서 가치가 높은 것은 거리가 짧은 것이다. 우선순위 큐를 통해서 항상 짧은 간선을 추출할 수 있다면 시간 복잡도를 더 줄일 수 있다.

구현

원리를 토대로 위의 사진의 start가 1인 경우의 다익스트라 알고리즘을 설계했다.

소스코드

import heapq
import sys

INF = int(1e9)

n, m = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline().strip())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  # 시작 노드로 가기 위한 최단 경로는 0이고 큐에 삽입
    distance[start] = 0  # 시작 노드 최단 경로는 0

    while q:
        dist, now = heapq.heappop(q)  # 가장 최단 거리가 짧은 노드에 대한 정보 추출
        if distance[now] < dist:  # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
            continue
        # 현재 노드와 연결된 다른 인접한 노드들 확인
        for item in graph[now]:
            cost = dist + item[1]  # 현재 노드 거쳐서 다른 노드로 이동하는 비용

            if cost < distance[item[0]]:  # 현재 노드를 거쳐서 다른 노드로 이동하는 비용이 더 작은 경우
                distance[item[0]] = cost  # 비용 최신화
                heapq.heappush(q, (cost, item[0]))  # 큐 삽입

dijkstra(start)

for i in range(1, n + 1):
    if distance[i] == INF:  # 접근할 수 없다면
        print('INFINITY')
    else:
        print(distance[i])  # 접근할 수 있다면

# 예제
# 6 11
# 1
# 1 2 2
# 1 3 5
# 1 4 1
# 2 3 3
# 2 4 2
# 3 2 3
# 3 6 5
# 4 3 3
# 4 5 1
# 5 3 1
# 5 6 2
# 3 3 4
# 3 3 5

출처

이것이 취업을 위한 코딩 테스트다 with 파이썬