[알고리즘] 다익스트라

다익스트라 (Dijkstra)

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

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

- 에지는 모두 양수

=> 음의 가중치가 없는 그래프의 한 노드에서 모든 노드까지의 최단 거리를 구하는 알고리즘

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

- 우선순위 큐를 사용

- 기본적으로 Greedy와 DP 알고리즘을 사용한 기법

1. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 (그리디)

2. 해당 노드로부터 갈 수 있는 노드들의 비용 갱신 (DP)

- 위의 두 단계를 반복하여 각 모든 노드 까지의 최단 거리를 구함

 

🌝 핵심 이론

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

- 인접 행렬로 구현도 가능하지만 시간 복잡도를 고려한다면 인접 리스트를 사용하는 것이 좋음

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

- 최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 아주 큰 값으로 초기화

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

- 최단 거리 배열에서 현재 값이 가장 작은 노드 고르기

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

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

- 1단계에서 저자해 둔 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트

- 연결 노드의 최단 거리는 다음과 같이 두 값 중 더 작은 값으로 업데이트

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

5. 3-4를 반복해 최단 거리 배열 완성하기

 

🌝 유의할 점

- 출발 노드와 도착 노드 간의 최단 거리를 구하는 것이 아닌 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현

BELATED ARTICLES

more