다익스트라 알고리즘

다익스트라는 그래프에서 한 노드로부터 각 노드까지의 최소 거리(간선 가중치의 합)을 구하는 알고리즘이다.

다익스트라 알고리즘은 각 노드를 방문하면서 전진할 수 있는 노드의 거리를 계산하고, 해당하는 노드에 대해 지금까지 구한 거리보다 작다면 갱신해주는 방법을 이용한다.

 

그래프가 주어지고 각각의 간선의 가중치가 주어졌을 때, 아래와 같은 방법을 따라 동작한다.

 

1. 출발 노드를 설정한다

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

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

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

5. 3번과 4번 과정을 반복한다.

 

글로만 알고리즘을 이해하기는 어렵고, 그림으로 이해해보자.

 

아래와 같은 그래프가 있다고 가정하자.

이미 방문한 노드는 빨간색으로 표시하고, 방문하지 않은 노드는 검은색으로 표시한다.

 

1번과 2번 동작에 의해 1번 노드를 출발 노드로 지정하고, 최단거리 테이블을 초기화 하였다.

여기서 최단거리의 의미는, 1번 노드가 출발 노드로 지정되었으므로 1번 노드부터 2~6번 노드까지 걸리는 최단 거리(가중치)를 의미한다.

초기화 시, 모든 노드까지의 가중치가 무한대(매우 큰 값)이라고 가정하고 초기화를 진행한다.

 

1번 노드와 1번 노드의 거리는 0이므로, 최단거리 테이블의 1번 거리 값을 0으로 바꿔준다.

 

다음으로, 최단거리 테이블에서 최솟값을 찾아보자.

1번 노드를 제외하고 모두 무한대 값으로, 1번 노드의 거리가 0으로 가장 작음을 알 수 있다.

그렇다면 1번 노드로부터 이동할 수 있는 모든 노드를 그래프에서 찾아보면 2번, 3번, 4번 노드로 이동할 수 있다는 것을 알 수 있다.

 

알고리즘의 의미가 출발 노드로부터 특정 노드까지 가는데에 필요한 거리(가중치)이므로 이는 곧 1번 노드를 거쳐 2번, 3번, 4번 노드로 이동한다는 의미이다. 따라서 1번에서 1번으로 가는 거리(가중치)인 0을 더해 2번, 3번, 4번 노드로 가는 거리(가중치)는 각각 (0+2), (0+5), (0+1)이다.

이 경우에서는 세 경우 모두 무한대보다 작으므로 최단거리 테이블의 값을 갱신해준다.

 

다음으로 다시 최단거리 테이블에서 최솟값을 찾아보니 4번 노드의 1임을 알 수 있다.

4번 노드에서 갈 수 있는 노드 경로를 그래프에서 찾아보니 3번과 5번 노드로 갈 수 있다.

이는 1번에서 4번을 거쳐 3번과 5번으로 가는데에 필요한 거리(가중치)이므로, 각각 (1+3), (1+1)임을 알 수 있다.

(이제부터 1번에서 1번을 거치는 가중치 0은 생략하기로 한다.)

 

+) 사실 이 과정에서 3번과 5번 노드에는 시작 노드로부터 해당 노드에 도달하는데에 필요한 '최소 경로(가중치)가 계속 누적되어 있다'

즉, 다이나믹 프로그래밍에서 메모이제이션과 같은 개념이 이미 들어가 있는 것으로, 다음 단계부터도 n번 노드를 방문하게 된다면 n번 노드의 값과 해당하는 거리(가중치)만 더해준다면, 이는 곧 출발 노드로부터의 최소 거리(가중치)를 모두 더해준 셈이 된다.

 

앞에서 계산한 (1+3)과 (1+1)은 이전에 있던 3번 노드와 5번 노드의 값인 무한대보다 작으므로 최단거리 테이블 값을 갱신해준다.

 

최단거리 테이블에서 최솟값을 다시 찾아보자.

이번에는 2번 노드의 2가 최솟값임을 알 수 있다. 5번 노드의 값도 동일한 2이지만, 관례상 노드 번호가 작은 것부터 따진다.

 

2번 노드에서 방문할 수 있는 노드는 4번 노드와 3번 노드이다.

4번 노드는 이미 방문했기 때문에 거리를 다시 계산하지 않고, 3번 노드는 (2+3)으로 기존 테이블에 있는 값인 4보다 큰 값이 나오므로 이 또한 갱신해주지 않고 넘어간다.

 

이번엔 다음 최솟값인 5번 노드의 2로 따져보자.

5번 노드에서 갈 수 있는 노드는 3번과 6번 노드로, 거리(가중치)를 계산하면 각각 (2+1)과 (2+2)이다.

 

기존의 3번 노드의 값은 4였으므로 3으로 갱신해주고, 6번 노드의 값은 무한대였으므로 4로 갱신해준다.

 

다음 최솟값은 3번 노드의 3이다.

3번 노드에서 갈 수 있는 경로를 살펴보면 2번 노드와 6번 노드이다.

 

2번 노드는 이미 방문한 노드이므로 계산하지 않고, 6번 노드로 가는 거리(가중치)를 계산하면 (3+5)이므로 기존 테이블 값인 6보다 크다. 따라서 갱신해 줄 필요가 없다.

 

6번 노드를 방문하고, 진행할 수 있는 노드가 없으므로 알고리즘이 종료된다.

 

결론적으로, 1번 노드로 부터 2~6번 노드로 가는 거리(가중치)의 최솟값은 각각 2, 3, 1, 2, 4 임을 알 수 있다.

 

INF = 999999999

# 전체 노드와 간선 개수 입력
node, weight = map(int, input().split())

# 시작 노드 입력
start = int(input())

# 방문 리스트 초기화
# 구현의 편의를 위해 1번 인덱스부터 노드번호와 맞추어 사용
visited = [False for _ in range(node+1)]

# 최단 거리 테이블
distance = [INF for _ in range(node+1)]

graph = [[] for _ in range(node+1)]

# 노드_간선 정보 입력
# i노드로부터 e노드까지 w만큼의 가중치가 존재
for _ in range(weight):
    i, e, w = map(int, input().split())
    graph[i].append((w, e))

# 최단거리 리스트 인덱스 반환
def get_least_value():
    min_value = INF
    index = 0
    for i in range(1, node+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    visited[0] = True
    visited[start] = True
    distance[start] = 0
    for nodes in graph[start]:
        distance[nodes[1]] = nodes[0]
    
    for _ in range(node-1):
        index = get_least_value()
        visited[index] = True
        for nodes in graph[index]:
            cost = distance[index] + nodes[0]
            if cost < distance[nodes[1]]:
                distance[nodes[1]] = cost
            else:
                continue

dijkstra(start)

print(distance)

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

[999999999, 0, 2, 3, 1, 2, 4]