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

다익스트라 알고리즘이란?

그래프 상에 음의 가중치가 없을 때!
최단경로를 찾기위한 알고리즘이다.

 

시작정점부터 다른 정점까지의 최단경로를 알 수 있음.

아 그리고 간선이 유향/무향 상관이 없다.

 

그래프 그림으로 설명을 해보면!

 

 

여기서 시작정점은 1이라고 설정을 하고, 나머지 정점2,3,4,5 까지의 최단경로를 찾는 방법!

 

1. 우선 정점을 모두 초기화 해야한다.
시작정점 : 0
나머지정점 : INF 으로 설정을 한다.
왜냐하면 시작하는 정점에서는 비용이 0이고, 나머지 정점은 갱신이 이뤄지지 않았으니 더 작은 값으로 바꿔주기 위해서 INF 무한으로 초깃값 설정을 한다!

 

초깃값 설정을 하게 되면 오른쪽 그래프와 같이 설정이 된다.
여기서 부터 최적화된 다익스트라를 사용하기 위해서 우선순위큐(이하 큐)를 사용하게 된다.
가장 작은 노드의 값을 꺼내기 위해서 이다.

 

처음 큐에 dist , vertex 를 넣게 된다. dist 순으로 작은 순서대로 꺼내기 위해!

 

그러면 정점 1을 넣고, dist 는 0 인 것을 넣게 된다.

 

2. 큐에서 정점 정보를 꺼내어 간선정보를 이용하여 나머지 정점들을 갱신한다.
우선 정점이 작은 순서대로 탐색을 한다고 하자.
이때 도착정점(there) 비용이 간선의비용+출발정점(here) 보다  크다면

 

if(  vertex[there] > here_there_cost + vertex[here] ) 

 

 

도착정점의 비용을 갱신한다.

 

갱신하며 갱신된 도착정점의 정보를 큐에 넣는다.

 

Q.push(make_pair(here_there_cost + vertex[here] , there))

 

 

 

큐에 top을 빼서 인접한 정점을 확인하고, pop을 한다.
위 그림에서는 정점 2와 4의 거리가 갱신되며, 큐에 넣게 된다.
이후 이 과정을 반복한다.

 

 

 

두번째 Q 에서 가장 비용이 적은 정점을 가진 것이 (비용, 정점)= ( 1 , 2 ) 정점2 이기때문에 꺼내고 인접한 정점들을 갱신시킨다.
그러면 정점3, 정점5 가 갱신이 되며, Q에 담는다.

 

 

 

인접한 정점이 갱신조건과 일치하다면 갱신시키고, 큐에 넣는다.

 

 

 

(비용, 정점) = (3, 3) 을 꺼내고 인접한 정점을 갱신시킨다.
정점4 를 갱신 시킬 수 있어 정점4를 큐에 넣는다.

 

 

 

(비용, 정점) = (3, 4) 를 꺼내어 인접한 정점을 갱신시킨다.
하지만 이 경우에 갱신을 할 수 없다.
그렇기 때문에 큐에 넣을 새로운 정점 또한 존재 하지 않는다.

 

큐의 다음 원소로 (비용, 정점) = (5, 4) 를 꺼낸다.

 

 

3. 하지만 이 경우에는 꺼낸 정보의 비용이 5이고, 현재 정점4의 비용은 3이기 때문에 해당 정점4의 정보는 가장 최단이며, 인접한 정점을 볼 필요도 없다.

 

 

while(!Q.empty()){
  pair<int, int> p = Q.top();
  Q.pop();
  int here = p.second;
  int cost = p.first;
  if(cost >= vertex[here]) continue;
  // source code
}

 

그렇기 때문에 if(cost >= vertex[here]) 인 경우가 발생하면 바로 다음 큐의 top을 꺼내기로 한다.

 

 

 

 

이제 큐에 마지막원소가 남았을 때, 또 갱신할 필요가 없는 상태이다.
그러므로 Q가 다 비워지면 시작정점1 부터 시작하여 다른 정점으로 이르는 거리가 최소비용으로 갱신이 된 것을 확인할 수 있다.

 

 

결과로 정점1부터 나머지로 이르는 최소비용인 것은
정점2 = 1
정점3 = 3
정점4 = 3
정점5 = 3
으로 결과가 나왔다.

 

그래서 순서를 요약하자면,
1. 정점 비용을 초기화 시킨다.
시작정점은 0
나머지 정점은 INF

2. 우선순위 큐 (priority_queue) 에 시작정점 비용 0 과 시작정점1을 집어 넣는다.
Q.push(make_pair(0, src));
priority_queue< pair<int, int> , vector<pair<int, int> > , greater<pair<int, int> > > Q;
라고 하게 되면 작은 순서대로 뽑아낸다.
그냥 우선순위 큐를 사용하게 되면, 큰 순서대로 뽑아낸다.

 

3. 이제 우선순위 큐가 비어있을 때까지 루프를 돌린다.
  3-0. 우선순위 큐에서 원소를 꺼낸다. (비용, 원소)
    3-0-0. 우선순위 큐에서 꺼낸 정점의 비용이 현재 저장된  비용보다 크다면
    3-0-1. 다시 3-0. 과정을 진행한다.
  3-1. 꺼낸 원소의 정점에서 인접한 정점을 갱신시킬수 있는지 확인한다.
  3-2. 갱신시킬  수 있다면, vertex[there] 정보를 갱신시킨다.
  3-3. 그리고 큐에 넣는다. 다시 3. 의 과정을 진행한다.

 

 

 

012345678910