다익스트라(Dijkstra)

다익스트라 알고리즘은 DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어에서 많이 사용되며, 개념적으로는 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이때 음의 간선을 포함할 수 없다.

 

물론 현실 세계에서는 음의 간선이 존재하지 않기때문에 다익스트라는 현실 세계에서 사용하기 매우 적합한 알고리즘인 것이다.

 

여기서 다익스트라 알고리즘이 왜 DP인지 궁금할 것이다. 그 이유는 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문에 작은 문제가 큰 문제의 부분 집합에 속해있기 때문이다. 즉, 다익스트라는 하나의 최단 거리를 구할 때, 그 이전까지의 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 그리고 다익스트라 알고리즘은 정렬 후에 가장 적은 것을 선택하는게 알고리즘에 포함이 된다. 이런 이유로 그리디 알고리즘으로 분류되기도 한다.

 

사실 다익스트라 알고리즘의 핵심 가치는 현재까지 알고있던 최단 경로를 계속해서 갱신하는 것이다.

 

그럼 이제 다익스트라 알고리즘의 작동 과정을 한번 살펴보자.

1. 출발 노드를 설정한다.
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
3. 방문하지 않은 노드중에서 가장 비용이 적은 노드를 선택한다.
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
5. 위 과정에서 3, 4번을 반복한다.

 

작성중..