[자료구조] 다익스트라 알고리즘

최단 경로를 구하는 방법은 다양하다. 

그 중 다익스트라 알고리즘에 대해 알아보자

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

각 경로의 가중치를 비교해서 최단거리 경로를 찾아내는 알고리즘이다.

가중치가 양수인 그래프에서 활용이 가능하며, 음수인 경우는 벨만-포드 알고리즘을 사용하면 된다

 

어떻게 작동할까?

다익스트라 알고리즘의 작동 과정은 다음과 같다.

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 초기화 한다. 이때 초기화 값은 inf 또는 아주 큰 수로 잡는다.

3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 찾고 해당 노드를 방문 처리한다.

4. 해당 노드를 거쳐 다른 노드로 넘어가는 가중치를 계산해 최단 거리 테이블을 업데이트 한다.

5. 3~4 과정을 최단 거리를 구할 때까지 반복한다.

 

예시를 보면서 확인하자

위와 같은 그래프가 있다고 치고 V0부터 각 노드들까지의 거리를 구해보자.

V0	V1	V2	V3	V4	V5
inf	inf	inf	inf	inf	inf

처음 최단거리 테이블은 이렇게 생겼다.

V0와 연결된 정점의 거리들을 갱신해보자.

V0	V1	V2	V3	V4	V5
0	2	inf	inf	inf	9

이제 V0와 연결된 정점인 V5까지의 거리를 갱신하면

아래와 같이 나타낼 수 있다.

V0	V1	V2	V3	V4	V5
0	2	inf	inf	inf	min(9,2+6) = 8

그럼 자동으로 V4의 값도 11로 확정이 되기에 V2를 갱신해보자.

V0	V1	V2	V3	V4	V5
0	2	10	inf	11	8

V4 -> V2 경로도 있기 때문에 한번 더 갱신을 해보면

V0	V1	V2	V3	V4	V5
0	2	min(10,11+7) = 10	inf	11	8

이렇게 갱신이 되고 마지막으로 V3를 구해보면

먼저 V2->V3로 놓고 수행해보자. 

V0	V1	V2	V3	V4	V5
0	2	10	11	11	8

다른 경로들과 비교해봤을 때 11보다 작은 경로가 없기 때문에 위와 같이 테이블이 확정이 된다.

 

다익스트라 알고리즘 의사코드

predecessor Dijkstra(G, start)
    // 1. 초기화
    for each 정점 v in G.V do
        distance[v] ← ∞
        predecessor[v] ← null
    distance[start] ← 0

    allowedVertices ← ∅       // 처리(허용)된 정점 집합

    // 2. 메인 루프: 모든 정점이 처리될 때까지
    while allowedVertices ≠ G.V do
        // 2.1. 아직 처리되지 않은 정점 중 거리 최솟값을 갖는 w 선택
        w ← argmin { distance[v] | v ∈ G.V \ allowedVertices }

        // 2.2. w를 처리 집합에 추가
        allowedVertices ← allowedVertices ∪ {w}

        // 2.3. w와 인접한 정점들의 거리 갱신
        for each v ∈ Adj[w] do
            if v ∉ allowedVertices then
                alt ← distance[w] + weight(w, v)
                if alt < distance[v] then
                    distance[v] ← alt
                    predecessor[v] ← w

    // 3. 결과 반환
    return distance, predecessor