알고리즘 - 다익스트라(Dijkstar)

다익스트라(Dijkstar)

---

그래프에서 최단 거리를 구하는 알고리즘 중 하나이다.

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

에지는 모두 양수로 이루어져 있어야 되며 출발 노드와 모든 노드 간의 최단 거리를 탐색한다.

 

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

인접 리스트

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

인접 행렬보다 인접 리스트로 구현하여 탐색하는 시간을 줄여야 한다.

최단 거리 배열

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

최단 거리 배열을 초기화 하고 1은 가중치가 없기 때문에 0으로 초기화한다.

컴퓨터는 무한대가 없기 때문에 큰 수로 지정해서 초기화 해준다. (예시는 편하게 무한대로 처리)

값이 가장 작은 노드 선택

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

가중치가 없어 0의 값을 가지는 1번 노드를 선택하여 해당 노드가 가리키는 다른 노드를 탐색하고 최단 거리를 구한다.

D[선택한 노드 인덱스] + 연관된 노드로 가는 가중치 < D[연관된 노드]

위의 예시처럼 1번 노드 인덱스의 값은 0이고 1번 노드가 가리키는 2번 노드로 가는 에지의 가중치는 8이다. 0과 8을 더하고 2번 노드 인덱스 값과 비교하여 더 작은 값으로 업데이트 해준다.

최단 거리 배열 업데이트

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

위의 예시에서 4번 노드 인덱스 값이 16에서 12로 바뀌는 것을 한 번 풀어보면 다음과 같다.

앞서 방문하지 않은 배열을 확인하고 가장 작은 값을 선택한다. (위의 사진에서 2번 노드를 선택)

D[2] + 4 < D[4] == 8 + 4 < 16 으로 계산이 가능하며 12는 16보다 작기 때문에 4번 노드 인덱스는 12 값으로 업데이트된다.