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

다익스트라 알고리즘이란?(What is a Dijkstra Algorithm?)

---

다익스트라 알고리즘은 가중치를 가지는 그래프에서 한 정점을 기준으로 다른 정점들에 도달하는 최단 경로를 찾는 알고리즘이다. 이때 중요한 것은 가중치가 음수를 가지면 안된다는 것이다. 가중치가 음수를 가지면 다익스트라 알고리즘이 동작할 수 없다. 다익스트라 알고리즘은 인접한 정점으로 가는 간선중 가장 적은 비용을 가지는 간선을 택한다. 알고리즘 수행중 새로운 경로가 생기면 그 경로를 기록하고 이후에 생기는 또 다른 경로와 비교하면서 최단 경로를 탐색한다.

 

 

다익스트라 알고리즘을 수행하기 위해서는 먼저 그래프를 인접 행렬로 표현해야 한다. 위 그림에서 인접 행렬을 보면 무한대 표시가 보인다. 이는 정점이 인접하지 않는다는 표시이다. 0은 출발하는 정점과 도착하는 정점이 서로 같다는 것을 의미하며 나머지 1 이상의 수는 각 정점으로 가는 간선의 가중치를 나타낸다.

 

다익스트라 알고리즘 수행 과정

---

다음은 다익스트라 알고리즘을 수행하는 과정이다.

 

1단계 : 0 방문

이 예시에서는 처음 방문하는 정점을 0으로 잡는다. 정점 0을 방문하면서 정점 0의 인접한 노드에 대한 최단 경로를 최소 비용 배열에 업데이트한다. 이때 무한대는 컴퓨터로 구현할 수 없기 때문에 적절한 수를 이용하여 무한대를 표현한다.(여기서는 모든 가중치의 합보다 큰 100을 쓰면 적절하다.)

 

 

 

 

 

2단계 : 2 방문

정점 0과 인접한 간선중 비용이 가장 작은 경로인 2로 가는 경로를 택하여 정점 2를 방문한다. 정점 2를 방문하면 2의 인접 정점인 5와 6으로 가는 경로가 생긴다. 0 -> 2 -> 5, 6으로 가는 최단 경로를 배열에 업데이트 한다. 노란색으로 칠해진 요소는 최소 비용이기 때문에 그대로 고정이 된다.

 

3단계 : 1 방문

다음 정점 1을 방문한다. 이때 1을 방문하면 4로 가는 경로가 생긴다. 배열에 0 -> 1 -> 4로 가는 최단 경로를 배열에 업데이트해준다.

 

 

 

4단계 : 3 방문

계속해서 가장 적은 비용을 가지는 간선인 정점 3을 방문한 후 배열을 업데이트해준다.

 

 

5단계 : 6 방문

다음 6을 방문한다. 6을 방문하면 5와 4로 가는 새로운 경로가 생긴다. 이때 기존에 경로와 새로 생긴 경로의 비용을 비교하여 가장 적은 비용의 경로로 업데이트한다. 이 경우에서는 0 -> 2 -> 6 -> 5의 경로는 기존 0 -> 2 -> 5의 경로보다 비용이 크기 때문에 교체하지 않지만, 0 -> 2 -> 6 -> 4의 경로는 기존 0 -> 1 -> 4의 경로보다 비용이 적기 때문에 비용이 적은 경로로 교체해준다.

 

 

6단계 : 5 방문

다음 정점 5를 방문한다. 

 

 

 

7단계 : 4 방문

다음 정점 4를 방문한다.

 

 

다익스트라 알고리즘 종료

이제 더 이상 방문할 정점이 없기 때문에 알고리즘은 종료된다. 우리가 알고리즘을 실행하면서 노란색으로 최소 비용을 표시했다. 노란색으로 표시된 경로는 이후에 정점의 최단 경로를 구성하는데 사용된다. 이것이 다익스트라 알고리즘의 특징이다.