[이것이 코딩 테스트다] 다익스트라 알고리즘 with Python

[이것이 코딩 테스트다] with Python

[이것이 코딩 테스트다] 다익스트라 알고리즘 with Python

Evolving Developer 2023. 5. 28. 13:52

🔒다익스트라 최단 경로 알고리즘

💡 그래프에서 여러 개의 노드가 있을 때,

💡 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

🔒특이점

음의 간선이 없을 때 정상 작동
- 음의 간선이란 0보다 작은 값을 가지는 간선
- 현실엔 음의 간선이 존재하지 않기 때문에 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택됨
다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류됨
각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 배열에 저장하며, 리스트를 계속 갱신함

✅알고리즘

💡 1. 출발 노드를 설정

💡 2. 최단 거리 테이블을 초기화

💡 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택

💡 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

💡 5. 위 과정에서 3번, 4번을 반복

✅다익스트라 알고리즘을 구현하는 두 가지 방법

💡 방법 1. 구현하기 쉽지만 느리게 동작하는 코드

💡방법 2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드

✅방법 1

✅이미 방문해 탐색을 마친 노드를 다시 방문하지 않기 위해 방문 여부를 저장하는 visited[] 배열 선언
- 처음에는 그 어떤 노드도 방문하지 않았단 의미에서 False로 초기화
- visited[0]을 제외한 visited[1] ~ visited[n]까지의 정보를 저장해야 하기 때문에 (n+1) 크기의 배열 생성
- visited = [False] * (n+1)
✅방문하지 않은 노드 중에서, 최단 거리가 가장 짧은 노드를 찾기 위해 get_smallest_node() 함수 선언
- 최단 거리를 저장하는 distance[] 배열에서 최단 거리를 찾고, visited[] 배열 값이 False인지 확인 후 반환

def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

✅get_smallest_node() 함수로 최단 거리가 가장 짧은 노드를 찾았다면, 이제 그 노드와 연결된 노드와 그 거리를 탐색하기 시작
- get_smallest_node()가 반환한 노드가 3번 노드이고, 3번 노드와 연결된 노드가 2, 5번 노드라면
- 시작 노드에서 2번, 5번 노드로 바로 가는 게 빠른지
- 1번 노드에서 3번 노드를 경유해 2, 5번 노드로 가는 게 빠른지 비교 후
- 더 작은 값으로 distance[2]와 distance[5] 업데이트
- 위 과정을 반복하며 더 짧은 경로를 찾을 때마다 distance[] 업데이트

💻 코드

import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수, 간선의 개수 입력받기
n, m = map(int, input().split())
# 노드의 시작 번호 입력받기
start = int(input())

# 노드 정보를 담을 그래프 만들기
graph = [[] for _ in range(n+1)]
# 방문한 적이 있는지 체크하는 리스트
visited = [False] * (n+1)
# 최단 거리를 모두 무한으로 초기화
distance = [INF] * (n+1)

# 노드와 간선 정보 입력받기
for _ in range(m):
    node1, node2, dis = map(int, input().split())
    graph[node1].append((node2, dis))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
# 반환된 노드를 기준으로 연결된 노드를 재탐색해야 하기 때문
def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

# 다익스트라 알고리즘
def dijkstra(start):
    # 시작 노드와 시작 노드 사이 거리는 0
    distance[start] = 0
    # 시작 노드와 연결된 노드와의 거리로 distance[] 초기화
    for node in graph[start]:
        distance[node[0]] = node[1]

    # 시작 노드를 제외한 (n-1)개의 노드에 대해서
    # 탐색하며 최단 경로를 업데이트 해야 하기 때문에 아래 과정을 (n-1)번 반복
    for i in range(n):
        # 방문하지 않았으며, 시작 노드에서 경로가 가장 짧은 노드 선택
        now = get_smallest_node()
        visited[now] = True
        # 선택 노드 기준으로 연결된 노드의 최단 거리를 탐색
        for node in graph[now]:
            # node[0] 노드까지 선택 노드를 경유해서 가는 최단 거리
            cost = distance[now] + node[1]
            # 경유해서 가는 방법이 최단 거리라면
            if cost < distance[node[0]]:
                # 거리 저장 배열을 수정
                distance[node[0]] = cost

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

✅방법 2

✅최단 거리가 가장 짧은 노드를 반환하는 get_smallest_node() 함수 대신 우선순위 큐 사용
- 우선순위 큐란 우선순위를 가진 데이터들을 저장하는 큐를 의미
- 데이터를 꺼낼 때 우선 순위가 높은 데이터가 가장 먼저 나온다는 특징
- heapq.heappush(배열, (거리, 노드))
- 위와 같이 저장하고 heapq.heappop()을 하면 자동적으로 거리가 가장 짧은 노드와 거리를 반환해준다.
✅이미 방문한 노드는 제외하기 위해 visited[] 배열 대신 아래 조건문 사용

# 방문할 노드를 가져오되, 이미 방문한 노드는 제외
dist, now = heapq.heappop(q)
# 방문할 노드
if distance[now] < dist:
    continue

어떻게 위와 같은 수식이 나올까? 예시를 들어보자.
만약 다음과 같은 그래프가 있다면
1 --1--> 2
1 --9--> 3
2 --1--> 3
시작 노드는 1이며, 노드 1과 노드 1의 사이 거리는 0이다.
- 우선순위 큐: (0, 1)
- heappop() -> (0, 1)
노드 1과 연결된 노드 2와 노드 3의 정보가 거리가 짧은 순으로 우선순위 큐에 담긴다.
- 우선순위 큐: (1, 2) (9, 3)
- heappop() -> (1, 2)
- distance[2] = 1, distance[3] = 9
노드 2와 연결된 노드 3의 정보가 우선순위 큐에 담기고, 노드 3으로 가는 최단 거리가 2로 수정된다.
- 우선순위 큐: (2, 3) (9, 3)
- heappop() -> (2, 3)
- distance[3] = 2
노드 3과 연결된 노드는 없으므로 그 어떤 것도 큐에 담기지 않는다.
- 우선순위 큐: (9, 3)
- heappop() -> (9, 3)
이때 distance[3] = 2이고, dist = 9이므로 distance[3] < dist를 충족하므로, 방문된 노드라고 판단하고 넘어간다.

💻 코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수, 간선의 개수 입력받기
n, m = map(int, input().split())
# 노드의 시작 번호 입력받기
start = int(input())

# 노드 정보를 담을 그래프 만들기
graph = [[] for _ in range(n+1)]
# 최단 거리를 모두 무한으로 초기화
distance = [INF] * (n+1)

# 노드와 간선 정보 입력받기
for _ in range(m):
    node1, node2, dis = map(int, input().split())
    graph[node1].append((node2, dis))

def dijkstra(start):
    # 방문할 노드를 우선순위 큐로 관리
    q = []
    # 시작 노드와 시작 노드 사이 거리는 0
    distance[start] = 0
    # 우선순위 큐에 시작 노드를 담고 시작
    heapq.heappush(q, (0, start))

    # 더이상 방문할 노드가 없을 때까지 반복
    while q:
        # 방문할 노드를 가져오되, 이미 방문한 노드는 제외
        dist, now = heapq.heappop(q)
        # 방문할 노드
        if distance[now] < dist:
            continue
        # 방문할 노드와 연관된 노드 정보 가져오기
        for node in graph[now]:
            # node[0]은 인덱스, node[1]은 거리
            # cost = 현재 노드까지의 최단 거리 + 새 노드로의 이동 거리
            cost = dist + node[1]
            # 만약 현재 노드를 경유해서 가는 방법이 기존 방법보다 더 최단 거리라면
            if cost < distance[node[0]]:
                # 최단 거리 업데이트
                distance[node[0]] = cost
                # 우선순위 큐에 연관 노드와 (예상) 최단 거리 삽입
                heapq.heappush(q, (cost, node[0]))

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

저작자표시 (새창열림)