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

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

 다익스트라 알고리즘이란 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 정점(노드)에서 다른 모든 정점으로 갈 수 있는 최단 경로를 알려준다. 최단 경로를 탐색하는 과정에서 현재까지 알고 있던 최단 경로를 계속해서 갱신해나간다는 특징이 있다. 목표 노드를 직접 선정하는 것이 아니라 출발 노드로부터 모든 노드의 최단 경로를 찾는 데 사용된다.

 

 만약 A, B, C 노드들이 있는데, A->C 거리보다 A->B + B->C 가 더 짧다면? A-> = A->B + B->C로 가정한다는 뜻이다(이걸 반복해서 최단 거리 탐색)

 

1. 탐색하지 않은 가장 가까운 정점을 방문

2. 그 정점과 이어진 정점을 방문하면서 최단 거리 계산

1번과 2번을 반복

 

 

- 다익스트라 작동 과정 - 

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

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

4. 해당 노드를 거쳐서 특정한 노드로 가는 경우 고려하여 최소 비용을 갱신한다.

5. 위 과정에서 3번~4번 반복한다.

 

 

 

 

 

 

 

출처: https://www.youtube.com/watch?v=611B-9zk2o4&t=3s

출처: https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98