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

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

그래프에서 출발 노드와 그 외 모든 노드 간의 최단 거리를 탐색하는 알고리즘

 

• 특징

- 에지가 모두 양수일 때 정상적으로 동작한다.

- 시간 복잡도 : O(ElogV) (노드 수 : V, 에지 수 : E)

 

 

다익스트라 알고리즘 핵심 이론

1. 인접 리스트로 그래프를 구현한다.

[ 예시 ]

- 인접 리스트에 연결한 배열의 자료형 : (노드, 가중치)

 

 

2. 최단 거리 배열을 초기화한다.

[ 예시 ]

- 출발 노드는 0, 이외의 노드는 무한(∞)으로 초기화한다.

 

* 무한(∞) : 문제에서 주어진 모든 에지의 합보다 충분히 더 큰 수

 

 

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 출발 노드로 설정한다.

[ 예시 ]

- 값이 0인 출발 노드에서 시작한다.

 

 

4. 선택한 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 배열을 업데이트한다.

[ 예시 ]

- 한 번 선택된 노드는 다시 선택되지 않도록 방문 배열을 만들어 확인한다.

 

• 최단 거리 업데이트 방법

Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값)

 

[ 예시 ]

D[1] + 8 < D[2]이면 ∞인 D[2] 값을 D[1] + 8로 업데이트한다.

D[1] + 3 < D[3]이면 ∞인 D[3] 값을 D[1] + 3으로 업데이트한다.

 

 

5. 모든 노드가 처리될 때까지 과정 3 ~ 4번을 반복해 최단 거리 배열을 완성한다.

[ 예시 ]

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.