[Computer Column] 다익스트라 알고리즘(dijkstra algorithm)

 

다익스트라 알고리즘이란?

다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다.
가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 적용된다.

의사 코드

def dijkstra(graph, edge, dist, start_vtx):
    # dist는 시작지점부터 다른 모든 노드들까지의 거리가 저장된 배열이다.
    # 시작지점을 제외한 나머지 부분은 무한대로 정의한다.
    dist = [INF for i in range(graph.size)]
    dist[start_vtx] = 0

    # 방문한 노드들을 담는 집합이다.
    visited = set()
    
    while (모든 노드들을 순회할 때까지):
        shortest_vtx = 방문하지 않은 노드 중 dist가 가장 짧은 것을 고른다.
        for (shortest_vtx에서 방문하지 않은 인접 노드에 대해):
            target = 인접한 노드 중 하나
            dist[target] = min(dist[target], dist[shortest_vtx] + edge[shortest_vtx][target])
        visited.push(shortest_vtx)

동작 방식

1번 정점부터 시작점으로 잡는다.
시작점에서 다른 노드들 까지의 거리를 배열로 나타내면 다음과 같다.

1. 경로가 가장 짧은 노드를 고른다. 여기서는 1번이다.
2. 갈 수 있는 노드가 무엇인지 확인한다. 1번 정점에서 갈 수 있는 노드는 2번과 3번이다.
3. 각각의 노드에 대해 dist[목표노드]와 dist[현재노드] + edge[현재노드][목표노드]를 비교한다.
4. 둘 중 가장 작은 값으로 갱신한다. 그럼 2번의 경우 INF와 (0 + 2 = 2)이므로 2, 3번의 경우 INF와 (0 + 3 = 3)이므로 3으로 갱신된다.
5. 1번은 더이상 방문하지 않는다.

이 후 dist의 변화는 다음과 같다. 직접 해보면 이해가 될 것이다.

복잡도

다익스트라 알고리즘의 주요 연산은 다음과 같다.

1. 경로가 가장 짧은 노드를 찾는다.
2. 미방문 노드 중 출발점으로부터의 최단 거리를 구한다.

맨 처음 고안된 버전은 일반 배열을 사용했기에 시간복잡도가 총 $$O(V^2)$$ 였다.
추후, 우선순위 큐를 이용하는 개선된 버전이 나와 $$O((V+E)logV)$$ 까지 줄어들었다.