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

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

그래프 내에서 최단경로를 정하는 알고리즘은 여러가지가 있습니다.

그 중 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구할 때 사용됩니다.

또한 모든 간선의 가중치가 양의 가중치를 가지고 있을 때 사용할 수 있습니다.

다익스트라의 기본적인 원리는 한 정점에서 갈 수 있는 다른 정점 중, 작은 가중치 간선을 우선적으로 탐색하는 방법입니다.

현재 정점을 A라 하고,  A와 연결된 가선이 B라고 가정해 봅시다.

A까지 이동하는 비용을 a ,  B까지 이동하는 비용을 b ,  A에서  B로 이동할 때 발생하는 비용 x  라 할 때

a+x < b 라면

B까지 가는 비용을 a+x로 갱신할 수 있습니다.

아래 예제를 통해 더 자세히 알아보겠습니다. 

위와 같은 그래프가 있고 시작점을 1번 정점으로 정하겠습니다.

시작 하기전에 dist배열을 선언하여 1번 정점에서 각 정점까지의 거리를 저장해놓겠습니다.

1	2	3	4	5
0	INF	INF	INF	INF

1번에서 시작하기 때문에 dist[1]은 0으로 초기화 하고 나머지는 모두 INF(무한) 으로 초기화 했습니다.

다익스트라는 기본적으로 BFS 탐색과 비슷하기 때문에 Queue를 이용하여 탐색합니다.

그러나 비용이 작은 것을 우선적으로 탐색할 것이기 때문에 우선순위 큐를 사용하면 편리합니다.

우선순위큐는 최소 힙(Min heap)을 이용하여 구현하겠습니다.

우선순위큐 STL의 사용법은 아래 주소를 참고하시길 바랍니다.

[http://koosaga.com/9]

우선, 모든 정점을 힙에 push 하겠습니다.

맨 상단의 데이터인, 1번 정점에서 연결된 다른 정점들을 확인해보겠습니다.

우선 1번 정점의 비용과 dist 배열의 비용을 비교하겠습니다.

만약 dist배열의 값이 더 작다면, 현재 값은 최소 비용이 아니므로 연결된 정점을 확인할 필요가 없습니다.

현재정점(1번)의 비용은 0, dist[1] 도 0이기 때문에 연결된 정점을 확인하겠습니다.

1번 정점과 연결된 정점은 2번, 3번 정점입니다.

여기서 위에서 설명한 다익스트라의 원리를 사용합니다.

2번까지의 비용 vs 1번까지의 비용 + 1번에서 2번으로 이동 비용

다음과 같이 나타낼 수 있습니다.

dist[2]  = min(dist[2] ,  dist[1] + adj[1][2])

만약 dist[1] + adj[1][2]가 더 작다면, 이 값으로 dist[2]을 갱신한 후 힙에 push 합니다.

본 예제에서는 dist[2] = min(INF , 0 + 2) 이므로

dist[2] = 2 로 갱신할 수 있고 {2(정점),2(비용)} 을 힙에 push 하겠습니다.

같은 방법으로 3번 정점도 확인해보면

dist[3] = min( dist[3] , dist[1] + adj[1][3]) 으로

dist[3] = 3 으로 갱신할 수 있습니다. 

갱신할 결과 dist배열과 큐는 아래와 같습니다. 

1	2	3	4	5
0	2	3	INF	INF

다시 pop하여 2번 정점을 확인해보겠습니다.

dist[2] = 2  / pop한 결과 2번정점 비용 =2 

두 값이 같으므로 2번 정점과 연결된 정점을 확인해보겠습니다.

2번 정점은 3번, 4번 정점과 연결되어있습니다.

dist[3] = min(dist[3] ,  dist[2] + adj[2][3]) 

dist[3] = min(3 ,  2 + 4 ) 이므로 갱신할 필요가 없습니다.

그러므로 이 값은 힙에 push하지 않고 넘어갈 수 있습니다.

다음으로 4번 정점은

dist[4] = min(dist[4] , dist[2] + adj[2][4] ) 

dist[4] = min(INF , 2 + 5 ) 이므로 dist[4]를 7로 갱신하고 힙에 push 하겠습니다.

1	2	3	4	5
0	2	3	7	INF

다음으로 3번 정점을 확인하겠습니다.

 dist[3] = 3 / Pop한 결과 3번 정점의 비용 = 3

같으므로 3번 노드와 연결된 정점, 4번 정점을 확인해보겠습니다.

dist[4] = min(dist[4] , dist[3] + adj[3][4] )

dist[4] = min( 7 , 3 + 6 ) 이므로 새롭게 갱신할 필요 없습니다.

다음 pop한 결과인 4번 정점은 연결된 정점이 없으니 Skip할 수 있습니다.

지금까지의 dist배열과 큐는 다음과 같습니다.

1	2	3	4	5
0	2	3	7	INF

2번 정점을 확인해보겠습니다.

dist[2] = 2  / Pop한 결과 2번 정점의 비용 = INF

dist배열의 값이 더 작으니 갱신할 필요가 없습니다.

큐에 남아있는 정점들도 같은 방법을 반복하면 됩니다.

이렇게 큐가 비워질때까지 각 정점까지의 비용을 갱신하면 최종 dist 배열을 얻을 수 있고

시작정점에서 모든 정점까지의 비용을 확인 할 수 있습니다. 

본 예제에서의 결과 dist 배열은 아래와 같습니다. 

1	2	3	4	5
0	2	3	7	INF

이해가 안되시거나 설명이 부족한 부분이 있다면 언제든 댓글 달아주시기 바랍니다!!