그래프 - 다익스트라

다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘입니다.

기능	특징	시간 복잡도(노드 수: V, 엣지 수: E)
출발 노드와 모든 노드간의 최단 거리 탐색	엣지는 모두 양수	O(ElogV)

 

특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있습니다.

 

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

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

(인접 행렬로 구현해도 좋지만 시간 복잡도 측면과 N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋습니다.)

2. 최단 거리 리스트 초기화하기

최단 거리 리스트를 만들고, 출발 노드는 0, 이외에 노드는 무한으로 초기화합니다.

(이때 무한은 적당히 큰 값을 사용하면 됩니다.)

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

최단 거리 리스트에서 현재 값이 가장 작은 노드를 구합니다.

(여기서는 값이 0인 출발 노드에서 시작하면 됩니다.)

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

선택된 노드에 연결된 엣지의 값을 바탕으로 다른 노드의 값을 업데이트합니다.

1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 엣지들을 탐색하고 업데이트하면 됩니다.

연결 노드의 최단 거리는 두 값 중 더 작은 값으로 업데이트합니다.

 

최단 거리 업데이트 방법

Min(선택 노드의 최단 거리 리스트의 값 + 엣지 가중치, 노드의 최단 거리 리스트의 값)

 

5. 과정 3~4를 반복해 최단 거리 리스트 완성하기