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

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

다익스트라 알고르즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만, 이 때 음의 간선을 포함할 수 없다. 

 

다익스트라 알고리즘이 다이마닉 프로그래밍 문제인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져있기 때문이다.' 작은 문제가 큰 문제의 부분 집합에 속했다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 

 

<동작 과정>

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

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

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

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

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

 

 

 

 

[참고]

https://blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘