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

다익스트라 알고리즘은 특정한 노드에서 다른 모든 노드의 최단거리를 구하는 알고리즘이다. 간선의 방향은 상관없지만 간선의 가중치가 음수이면 해당 알고리즘은 사용할 수 없다. 이러한 점 때문에 내비게이션, GPS 등에 많이 이용되는 알고리즘이다.

 

다익스트라 알고리즘은 2가지 방법으로 구현이 가능한데 1번째 방법은 O(V^2)의 시간복잡도를 가지고, 나머지 하나는 우선순위 큐를 이용하여 O(ElogV)의 시간 복잡도를 가지게 된다.

 

다익스트라 알고리즘의 순서는 다음과 같다.

• 출발 노드를 지정한다.
• 최단 거리 테이블의 값을 무한으로 설정한다.
• 방문하지 않은 노드 중에 최단 거리 테이블에서 가장 작은 값을 가진 노드를 선택한다.
• 해당 노드에서 다른 노드의 거리를 계산하여 최단 거리 테이블의 값을 갱신한다.
• 위의 3, 4번 과정을 반복한다.

다음은 다익스트라 알고리즘의 동작 원리를 설명한 그림이다. 파란색 노드는 방문 완료한 노드이다. 초록색은 계산 중인 노드이다. INF는 무한 값이다.

 

다익스트라 알고리즘 1번째

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

 

다익스트라 알고리즘 2번째

출발 노드에서 출발 노드까지의 거리는 0이기 때문에 출발 노드를 선택한다. 출발 노드와 연결된 다른 노드로 가는 최단 거리 비용을 계산한다. 2번 노드 최단 거리 (0+1), 5번 노드 최단 거리 (0+5), 6번 노드 최단 거리 (0+6) 이므로 각각의 값으로 갱신한다.

 

다익스트라 알고리즘 3번째

다음은 방문하지 않은 노드 중에 최단 거리 값을 가지고 있는 2번 노드를 선택한다. 2번 노드와 연결된 다른 노드로 가는 최단 거리 비용을 계산한다. 4번 노드 최단거리 (1+2), 5번 노드 최단거리 (1+3) 이므로 각각의 값으로 갱신한다.

 

다익스트라 알고리즘 4번째

다음은 방문하지 않은 노드 중에 최단 거리값을 가지고 있는 4번 노드를 선택한다. 4번 노드와 연결된 다른 노드로 가는 최단 거리 비용을 계산한다. 4번 노드에서 더 짧게 이동할 수 있는 노드가 없다.

 

다익스트라 알고리즘 5번째

다음은 방문하지 않은 노드 중에 최단 거리값을 가지고 있는 5번 노드를 선택한다. 5번 노드와 연결된 다른 노드로 가는 최단 거리 비용을 계산한다. 3번 노드 (4+2), 6번 노드 (4+1) 이므로 각각의 값으로 갱신한다.

 

다익스트라 알고리즘 6번째

다음은 방문하지 않은 노드 중에 최단 거리값을 가지고 있는 6번 노드를 선택한다. 6번 노드와 연결된 다른 노드로 가는 최단 거리 비용을 계산한다. 4번 노드에서 더 짧게 이동할 수 있는 노드가 없다.

 

다익스트라 알고리즘 7번째

다음은 방문하지 않은 노드 중에 최단 거리값을 가지고 있는 3번 노드를 선택한다. 3번 노드와 연결된 다른 노드로 가는 최단 거리 비용을 계산한다. 3번 노드에서 더 짧게 이동할 수 있는 노드가 없다.

 

다익스트라 알고리즘 8번째

최단 거리 테이블의 값에 따르면 1번 노드에서 2번, 3번, 4번, 5번, 6번 노드로의 최단 거리는 각각 1, 6, 3, 4, 5이다.