Dijkstra

출발점과 도착점 사이의 최단경로 문제를 푸는 알고리즘이다.

단, 조건은

• 어떤 변도 음수 가중치를 갖지 않는다.

• 유향그래프이다.

예를 들어 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타낸다고 하자. 변들이 도시 사이를 이동하는 가중치를 나타낸다면, 다익스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다.

개념

다익스트라 알고리즘은 각 꼭짓점 v에 대해 시작점 s에서 v까지의 최단 거리 d[v]를 저장하며 작동한다. 시작시 d[s]=0이다. 시작점을 제외한 모든 d[v]=무한대다. 즉 최단 경로를 모른 다는 표시다. 알고리즘 종료시 d[v]는 s에서 v까지의 최단경로를 나타낸다. 만약 경로가 존재하지 않으면 무한대로 남아있다.

다익스트라는 변 경감(edge relaxation)이라는 연산을 바탕으로 한다. s에서 u까지의 최단경로 d[u]를 이미 알고 있고, u에서 v까지 가중치가 존재할 때, s에서 v까지의 최단 경로는 d[u](u까지의 최단경로) + (u,v) 를 추가하여 얻을 수 있다. MIN(d[u] + (u,v) ,d[v])를 통해 d[v] 값을 결정한다. 경감 연산은 모든 변 (u,v)에 대해 한번씩 경감이 적용되어 모든 d[v]가 최단 경로 비용을 나타내게 되었을 때 끝난다.

수행 과정

1. 시작 정점에서 방문하지 않은 인접한 정점들을

2. 방문하지 않은 정점들 중 거리(dist)가 가장 짧은 정점을 선택(current)해 방문

3. 해당 정점(current)에서 인접하면서 방문하지 않은 정점들(adj)의 거리를 갱신

   • 해당 정점(v)에 저장된 최단 거리 VS 기준 정점(u)까지의 최단 거리 + (u,v)

4. 2번 수행 완료 후, dist가 가장 작은 정점을 선택하여 2번 반복

수행 과정 중 2번을 구현할 때, 아직 방문하지 않은 정점 중 가장 짧은 정점을 어떻게 선택할까? 단순하게는 dist 값들을 전부 비교하면 매번 O(V), 루프는 V-1번 실행되므로 O(V^2)의 시간복잡도가 발생한다. 이는 너무 크다. 여기서 우선순위 큐를 사용하면 시간복잡도를 줄일 수 있다. 먼저, 최소힙을 사용하자. 한개 정점 방문시, 인접한 정점 v의 dist를 갱신할 때마다 최소힙에 (dist[v],v) 를 넣는다. 비교 기준은 dist 값의 오름차순으로 한다. 이런식으로 구현하면, v 방문하기 전에 값이 여러 번 갱신 될 수 있고, 서로 다른 (d,v) 값들이 우선순위 큐 안에 존재한다. 하지만, .top()으로 가장 작은 값 하나만 사용하고 방문 flag를 통해 무시하고 다음 .top()을 사용하면 된다.

우선순위 큐를 사용하면 V^2개의 정보가 들어 있다고 해도 원래 연산에 O(log N)의 시간이 소요되는 우선순위 큐 입장에서 O(log(V^2)) = O(2logV) = O (logV)가 된다. 인접 정점으로 거리 갱신하는 부분은 O(E)이므로, 시간복잡도의 합은 O(E+VlogV)다.

const int INF = 10000;

int dist[20001], start;
bool isVisited[20001];

class CompareCost{
public:
    bool operator()(pair <int, int> n1, pair <int, int> n2){
      return n1.second > n2.second;
    }
};

vector <pair<int, int> > edges[300001];
priority_queue <pair<int, int>, vector<pair<int, int> >, CompareCost> pq;

void dijkstra(){
  pq.push(make_pair(start, 0));
  dist[start] = 0;

  while(!pq.empty()){
    int from;
    do {
      from = pq.top().first;
      pq.pop();
    }while(!pq.empty() && isVisited[from]);

    isVisited[from] = true;

    for(int i=0; i<edges[from].size(); i++){
      int to = edges[from][i].first;
      int cost = edges[from][i].second;

      if(dist[to] > dist[from] + cost){
        dist[to] = dist[from] + cost;
        pq.push(make_pair(to, dist[to]));
      }
    }

  }
}

int main(){

  int N,M, from, to, cost;

  scanf("%d %d", &N,&M);
  scanf("%d", &start);

  fill_n(dist, N+1, INF);

  for(int i=0; i<M; i++){
    scanf("%d %d %d", &from, &to, &cost);
    edges[from].push_back(make_pair(to,cost));
  }

  dijkstra();

  for(int i=1; i<=N; i++){
    if(dist[i]==INF){
      printf("INF\n");
    }
    else{
      printf("%d\n", dist[i]);
    }

  }
}

summary

다익스트라는 음수 가중치를 갖지 않는 유향 그래프에서 최단경로 문제를 푸는 알고리즘이다.

1. 모든 정점을 무한대로 초기화

2. 시작 정점의 최단거리(dist) 0으로 할당. 시작정점을 큐에 추가

3. 큐에서 가장 작은 dist를 가진 정점(current) 추출 및 방문 Flag 체크

   • 이미 방문한 서로 다른 (v, cost)쌍을 while문을 통해 pop한다.

4. current 정점과 인접하면서 + 방문하지 않은 정점(v)들을 다음 기준을 만족시 큐에 추가

   • dist[current] + cost(u,v) < dist[v]

5. 3~4번을 큐가 비어있을 때까지 반복

관련문제