[Algorithm] Dijkstra Algorithm (다익스트라 알고리즘)

1. 다익스트라 알고리즘

다익스트라 알고리즘은 가중치가 있는 그래프에서, 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘이다. 

이는 특정 지점까지의 거리 = A까지 가는 거리 + A에서 특정 지점까지 소요되는 거리 라는 아이디어를 기반으로 한다. 

과정을 살펴보면 다음과 같다.

 

1) 거리 배열을 최댓값으로 초기화하고, 출발지의 값만 0으로 설정한다.

2) 현재 방문하지 않은 정점 중 가장 거리 값이 작은 지점을 선택한다.

3) 해당 지점과 인접한 지점들의 거리를 갱신한다.

4) 모든 지점이 선택될 때 까지, 2와 3을 반복한다.

 

다음 그래프를 통해 살펴보자. 자세한 설명은 다음 링크를 참고하면 된다. 많은 도움을 받았다.

https://www.codetree.ai/missions/6/concepts/37/problems/ga-dijkstra/introduction

코드트리

인접한 지점들과의 거리를 갱신한다는 점에서 큐를 사용하여 구현할 수 있다. 인접한 지점들을 모두 방문하고, 방문된 지점들에 대해 거리를 갱신해야 하기 때문이다. 이진 트리에서 생각해보면, 인접한 지점들을 모두 방문한다는 것은 자식 노드를 모두 방문한다고 생각할 수 있다. 또한 방문한 노드들에 대해 다시 그 노드들의 거리를 갱신하는 것은 이진 트리에서 모든 자식들을 방문한 이후 자식 노드에 대해 다시 탐방을 수행하는 과정이다. 따라서 큐를 사용한다. 모든 노드들을 큐에 넣어놓은 뒤, 시작점, 즉 첫 번째 노드부터 pop하며 순회하면서 최단 거리를 구하면 마지막엔 모든 노드들에 대한 최단 거리를 구할 수 있다. 

 

2. 구현

 

from collections import deque

n = int(input())
graph = []

for i in range(n):
    graph.append(input().split())
for i in range(n):
    for j in range(n):
        graph[i][j] = int(graph[i][j])

dist = [float("inf") for _ in range(n)]
dist[0] = 0

q = deque()

for i in range(n):
    q.appendleft(i)

while len(q) > 0:
    present, mindist = 0, float("inf")
    for item in q:
        if dist[item] < mindist:
            present = item
            mindist = dist[item]
    print(present)
    q.remove(present)

    for i in range(n):
        if graph[present][i] != 0:
            tmp = dist[present] + graph[present][i]
            if tmp < dist[i]:
                dist[i] = tmp
    print(dist)