최단경로 - 다익스트라 알고리즘 구체적인 설명

다익스트라 알고리즘은 하나의 출발 노드로부터 모든 노드까지의 최단 경로를 찾는 알고리즘입니다.

 

알고리즘의 원리를 간략히 설명하면 다음과 같습니다.

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

 

눈으로 읽어보면 해당 원리를 이해하기엔 쉽지 않습니다.

예시를 들어서 원리를 설명드리겠습니다.

 

예시 그래프입니다.

예시 노

노드 개수 (n) = 6
간선 개수 (m) = 9

시작 노드 (start) = 1

간선 정보:
1 -> 2 (비용: 2)
1 -> 3 (비용: 5)
2 -> 3 (비용: 2)
2 -> 4 (비용: 3)
2 -> 5 (비용: 7)
3 -> 5 (비용: 8)
4 -> 5 (비용: 1)
4 -> 6 (비용: 4)
5 -> 6 (비용: 3)

 

1. 출발 노드 설정

출발 노드를 설정합니다. 이 예시에서는 시작 노드를 1로 설정했습니다.

 

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

• 시작 노드로부터 각 노드까지의 최단 거리를 저장하는 테이블을 초기화합니다.
• 시작 노드 자신까지의 거리는 0으로, 나머지 노드까지의 거리는 무한대(INF)로 초기화합니다. 

노드 1: 0
노드 2: INF
노드 3: INF
노드 4: INF
노드 5: INF
노드 6: INF

 

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

• 초기에는 시작 노드인 1번 노드가 선택됩니다.
• 시작 노드부터 가장 짧은 거리로 갈 수 있는 노드를 선택합니다.

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

• 선택한 노드(1번 노드)를 기준으로 연결된 간선을 확인하고, 다른 노드로 가는 비용을 계산합니다.
• 현재 선택한 노드(1번 노드)를 거쳐 다른 노드로 가는 거리를 계산합니다.
• 계산한 거리가 해당 노드까지의 현재 최단 거리보다 짧을 경우, 최단 거리 테이블을 갱신합니다.

# 1번 노드를 거쳐서 2번 노드로 가는 거리

 

노드 1: 0
노드 2: 2
노드 3: INF
노드 4: INF
노드 5: INF
노드 6: INF

 

# 1번 노드를 거쳐서 3번 노드로 가는 거리를 계산합니다. 현재 3번 노드까지의 최단 거리가 INF이므로 갱신합니다.

노드 1: 0
노드 2: 2
노드 3: 5
노드 4: INF
노드 5: INF
노드 6: INF

 

5. 다음 노드 선택 및 갱신 반복

• 이제 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다.
• 현재 선택한 노드로부터 갈 수 있는 노드까지의 최단 거리를 계산하고, 갱신합니다.
• 이 과정을 반복하여 모든 노드에 대한 최단 거리를 계산합니다.

다음으로 방문할 노드를 선택합니다.

선택 기준은 아직 방문하지 않는 노드 중에 최단 거리가 가장 짧은 노드를 선택하는 것입니다.

현재까지의 상태에서 최단거리가 가장 짧은 노드는 2번 노드입니다.

 

6. 2번 노드 선택 및 갱신

• 2번 노드를 선택합니다.
• 2번 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.

2번 노드를 거쳐서 3번 노드로 가는 거리 계산

현재 3번 노드까지의 최단 거리는 5이고, 2번 노드에서 3번 노드로 가는 비용은 2이므로(2+2 =4)가 됩니다.

이 값은 현재 3번 노드까지의 최단 거리보다 짧으므로 최단 거리 테이블을 갱신합니다.

노드 1: 0
노드 2: 2
노드 3: 4
노드 4: INF
노드 5: INF
노드 6: INF

 

---

 

이런식으로 출발 노드로부터 다음 노드를 선택하고 최단 거리를 갱신하는 과정을 반복하면, 최종적으로 모든 노드로 가는 최단 경로가 계산됩니다.

 

 

파이썬 코드로 표현해보겠습니다.

---

import sys

input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정합니다.

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())

# 시작 노드 번호를 입력받기
start = int(input())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]

# 방문한 적이 있는지 체크하는 목적의 리스트 만들기
visited = [False] * (n + 1)

# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))


# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환하는 함수
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):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
    for i in range(n - 1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 다른 노드를 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:
                distance[j[0]] = cost


dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

 

graph 예시 시각화

graph = [
    [],                  # 노드 0은 사용하지 않으므로 비어있습니다.
    [(2, 1), (3, 4)],    # 노드 1에서 노드 2로 가는 비용은 1, 노드 3으로 가는 비용은 4입니다.
    [(1, 1), (3, 2), (4, 3)],  # 노드 2에서 노드 1로 가는 비용은 1, 노드 3으로 가는 비용은 2, 노드 4로 가는 비용은 3입니다.
    [(1, 4), (2, 2), (4, 5)],  # 노드 3에서 노드 1로 가는 비용은 4, 노드 2로 가는 비용은 2, 노드 4로 가는 비용은 5입니다.
    [(2, 3), (3, 5)]     # 노드 4에서 노드 2로 가는 비용은 3, 노드 3으로 가는 비용은 5입니다.
]

각 노드 번호를 인덱스로 사용하며, 해당 노드에서 다른 노드로 가는 비용을 튜플(목표 노드, 비용) 형태로 저장하고 있습니다. 

 

예를 들어, graph[1]  은 노드1에서 출발하여 노드2와 노드3으로 가는 경로 및 비용을 저장하고 있습니다.

이러한 graph 배열을 통해 각 노드에서 어떤 노드로 가는 경로와 비용을 효율적으로 관리하고 최단 경로를 계산할 수 있습니다.