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

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

다익스트라 알고리즘은 DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다.
인공위성, GPS 등 현실 세계에서 굉장히 많이 사용되며, 다음과 같은 특징들이 있다.

• 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.
• 음의 간선을 포함할 수 없다 (이 경우 벨만 포드 알고리즘 사용)
• $O(NlogN)$의 시간 복잡도를 가진다.

 

동작 단계

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 초기화한다.

3. 현재 위치한 노드의 인접 노드 중 아직 방문하지 않았고, 거리가 가장 짧은 노드를 선택한다.

4. 선택된 노드를 방문처리한다.

5. 해당 노드를 거쳐 다른 노드로 넘어가는 간선의 가중치를 통해 최단 거리 테이블을 업데이트한다.

6. 3~5 과정을 반복한다.

 

최단 거리 테이블은 N번 노드까지 도달하는데 필요한 최단 거리를 기록한다.

 

동작 예시

먼저 최단 거리 테이블을 초기화하고, 인접 리스트를 생성한다.

출발 노드의 거리를 0으로 설정한다.

 

출발 노드와 인접한 노드인 2,4를 기존 거리값과 비교해 최솟값으로 업데이트 한다.

 

아직 방문하지 않은 노드 중 가장 거리가 짧은 노드인 4번 노드를 선택하고,

인접 노드인 2번과 5번 노드를 갱신한다.

2번 노드는 기존 거리인 2가 새롭게 추가된 거리 3짜리 경로보다 짧으므로 기존 거리를 택한다.

아직 방문하지 않은 노드 중 가장 거리가 짧은 노드인 2번 노드를 선택하고,

인접 노드인 3번과 4번 노드를 갱신한다.

아직 방문하지 않은 노드 중 가장 거리가 짧은 노드인 5번 노드를 선택하고,

인접 노드인 6번 노드를 갱신한다.

아직 방문하지 않은 노드 중 가장 거리가 짧은 노드인 6번 노드를 선택한다.

현 문제에서는 6번 노드가 도착 노드이므로 다익스트라를 중단한다.

 

reference

• https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://m.blog.naver.com/ndb796/221234424646