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

다익스트라 알고리즘

 다익스트라 알고리즘은 다이나믹 프로그래밍를 활용한 최단 경로(Shortest path) 탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.

 

 다익스트라 알고리즘이 다이나믹 프로그래밍을 활용하는 이유는 '최단 거리는 다양한 루트가 존재하기 때문'이다. 그렇기에 기존에 하나의 최단 거리를 구할 때 까지 모든 루트를 그대로 사용한다.

 

 

 아래의 그래프에서 1에서 다른 정점으로 가는 최단 거리를 구한다고 해보자.

1에서 각 정점으로 한 번에 가는 최단 거리는 각 3, 6, 7이다. 이 때 한 번에 가는 것이 아닌 2를 거쳐 정점 3과 정점 4로 간다면 3 > 1과 3 > 1 > 1로 각 4와 5로 더욱 짧은 거리를 구할 수 있다.

 

해당 방법을 단계화하면 아래와 같다.

  1. 출발 노드를 설정합니다.

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

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

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

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

 

이 방법을 더욱 복잡한 예시로 적용해보자

 

위 그래프를 각 정점에서 다른 정점으로 가는 비용을 테이블로 나타내보자 이 때 행에서 열로 가는 비용을 테이블에 나타낸다.

 

우리가 구하고자 하는 것은 점 1에서 다른 점으로 가는 최단 거리이다. 그렇기에 1행을 따로 나타내면 아래와 같다.

 

이제 위에서 단계화 한 과정을 적용해보자. 

각 점 중 최단 거리에 있는 점 4를 선택하고, 해당 노드를 거쳐서 다른 노드로 가는 최단 거리를 구해보자

점 1 > 점 2 = min ( 2, 1 + 2) = 2

점 1 > 점 3 = min ( 5, 1 + 3) = 4

점 1 > 점 4 = min ( 1 ) = 1

점 1 > 점 5 = min ( 무한, 1 + 1 ) = 2

점 1 > 점 6 = min ( 무한, 1 + 무한 ) = 무한

 

위 계산을 통해 새로운 최단 거리를 구할 수 있다. 이를 테이블에 적용하면 아래와 같다.

 

이제 이 방법을 반복하여 사용해보자. 방문하지 않은 점 중 최단 거리를 가지는 점 2을 계산해보자.

점 2를 계산하더라도 변하는 값은 없다.

 

 

다음 최단 거리인 점 5로 계산해보자.

 해당 과정을 통해서 점 6으로 가는 방법이 무한 => 4로 변경되고, 점 3으로 가는 방법이 4 => 3으로 변경이 된다.

 위 방법을 모든 점에 적용하면 최종적으로 아래와 같은 최단 거리 테이블이 나온다.