그래프 : 다익스트라

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

그래프에서 최단 거리를 구하는 알고리즘

 

- 기능 : 출발 노드와 모든 노드간의 최단 거리 탐색

- 특징 : 에지는 모두 양수

- 시간 복잡도 : O(ElogV)

 

* V : 노드 수, E : 에지 수

 

 

다익스트라 원리

1. 인접 리스트로 그래프 구현하기

 

2. 최단 거리 배열 초기화하기

최단 거리 배열을 만들고 출발 노드는 0, 이외의 노드는 무한으로 초기화한다.

-> 무한은 적당히 큰 값을 사용하면 됨

시작점을 1이라고 가정

 

3. 값이 가장 작은 노드 고르기

최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 여기서는 값이 0인 출발 노드에서 시작

 

4. 최단 거리 배열 업데이트하기

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

 

5. 3~4번을 반복해 최단 거리 배열 완성하기

이때 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리하고, 모든 노드가 선택될 때까지 반복하면 최단거리 배열이 완성됨

 

 

정리

1. 다익스트라는 출발 노드와 그외 노드 간 최단 거리를 구하는 알고리즘

2. 에지는 항상 양수여야 함

3. 출발 노드와 도착 노드간의 최단 거리가 아닌, 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현함!!