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

Dijkstra 알고리즘은 단일 시작점에서 모든 정점으로의 거리를 구하는 알고리즘이다.

 

다음과 같은 그래프가 주어졌다고 하자.

해당 그래프는 인접 행렬(Adjacency Matrix) W로 구현되어 있다.

시작점은 1번이다.

위 그림에서 dist 배열은 시작점에 해당하는 1번 정점으로부터의 거리를 나타낸다.

dist[i] : 1번 정점으로부터 i번 정점까지의 거리

dist 배열의 각 원소를 INF로 초기화 한다.

 

우선, 시작점에서 시작점으로의 거리를 0으로 설정한다.

그리고 시작점에 인접한 정점들의 거리를 갱신한다.

위 사진의 경우 1번 정점은 2번 정점과 3번 정점에 인접해있다.

정점까지의 거리는 각각 2와 3이다.

 

Dijkstra 알고리즘의 핵심은 dist[j]를 구할 때, 특정 경유지(예를 들어 i)를 거쳐서 가는것이 가까운지

아니면 현재 알고있는 거리 dist[j]가 더 가까운지 비교하는데에 있다.

의사코드로 표현하자면 다음과 같다.

 

dist[j]=min(dist[j],dist[i]+W[i][j])

 

경유지를 시작점인 1번 정점으로 하고, dist[1]은 0으로 설정했으므로 2번 정점과 3번 정점에 대해서도

위 식을 적용시켜볼 수 있다.

 

dist[2]=min(dist[2],dist[1]+W[1][2])=min(INF,0+2)=2

dist[3]=min(dist[3],dist[1]+W[1][3])=min(INF,0+3)=3

 

위 과정을 진행하면 다음과 같이 dist 배열이 갱신된다.

위 과정에서 dist[2]와 dist[3]의 갱신이 이루어졌다.

갱신이 발생한 두 정점 중 더 작은 dist 값을 갖는 정점인 2번 정점의 주변 정점까지의 거리를 갱신하고자 한다.

2번 정점과 인접한 정점은 3번과 4번 정점이다. 

3번 정점을 우선 살펴보자.

 

dist[3]=min(dist[3],dist[2]+W[2][3])=min(3,2+4)=3

 

이므로 갱신이 발생하지 않았다. 다음으로 4번 정점을 살펴보자.

 

dist[4]=min(dist[4],dist[2]+W[2][4])=min(INF,2+5)=7

 

로 갱신이 이루어졌다. 4번 정점이 갱신된 dist 배열의 모습은 아래와 같다.

현재 갱신이 발생했던 정점은 3번과 4번이다.

이번에도 마찬가지로 dist값이 제일 작은 3번 정점에서 주변 정점까지의 거리를 갱신하겠다.

 

3번 정점에 인접한 정점은 4번이다.

 

dist[4]=min(dist[4],dist[3]+W[3][4])=min(7,3+6)=7

 

이므로 갱신이 일어나지 않았다.

그러면 이번엔 4번 정점에서 주변 정점까지의 거리를 갱신해보도록 하겠다.

4번 정점은 인접한 정점이 없기때문에 갱신할 것이 없다.

 

따라서 dist 배열은 다음과 같다.

Dijkstra 알고리즘에서 한 정점에서 주변 정점까지의 거리를 구한 후,

다음에는 어떤 정점을 기준으로 살펴볼까하는 문제가 발생한다.

 

여기서는 Min-Heap으로 구현된 우선순위 큐(Priority Queue)가 적합하다.

이때 중요한 것은 dist 배열의 갱신이 이뤄진 경우에만 Queue에 삽입되어야 한단 것이다.

 

그렇지 않으면 갱신이 일어나지 않더라도 인접한 정점이 존재한다면

인접한 정점을 계속 Queue에 삽입하기 때문에 무한루프에 빠질 것이다.