0x1D. 다익스트라 알고리즘 - 최단 경로 탐색

0x1D 다익스트라

0x00 알고리즘 설명

다익스트라 알고리즘 = 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 (이론적 분석은 최단 경로 알고리즘 참고) Negative weight 허용 X

0x01 구현

기본 구현 (비효율적)

vector<pair<int, int>> adj[20000];
const int INF = 0x3f3f3f3f;
bool fix[20000];
int d[20000];
int v = 10;

void dijkstra_naive(int st){
  fill(d, d+v+1, INF); // 원본 그래프의 간선 데이터를 초기화
  d[st] = 0;
  while(true){
    int idx = -1;
    for(int i = 1; i <= v; i++){
      if(fix[i]) continue;
      if(idx= -1) idx= i;
      else if(d[i] < d[idx]) idx= i;
    }
    if(idx= -1 || d[idx]= INF) // 더 이상 선택할 정점이 없으면
      break;
    fix[idx]= 1; // 현재 idx 고정
    for(auto nxt : adj[idx])
      d[nxt.first]= min(d[nxt.first], d[idx] + nxt.second);
  }
}

O(V^2 + E) 이기 때문에 최적화 필요

우선순위 큐를 활용한 최적화

1. 우선순위 큐에 (0, 시작점)을 추가
2. 우선순위 큐에서 거리가 가장 작은 원소를 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우 넘어감
3. 원소가 가리키는 정점을 v라고 할 때, v와 이웃한 정점들에 대해 최단 거리 테이블 값보다 v를 거쳐가는 것이 더 작은 값을 가질 경우 최단 거리 테이블의 값을 갱신하고 우선순위 큐에 (거리, 이웃 정점)을 추가
4. 우선순위 큐가 빌때까지 2, 3번을 반복

BOJ 1753: 최단경로

#include<bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int v,e,st;

// {비용, 정점 번호}
vector<pair<int,int>> adj[20005];
const int INF = 0x3f3f3f3f;
int d[20005]; // 최단 거리 테이블
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> v >> e >> st;
  fill(d,d+v+1,INF);
  while(e--){
    int u,v,w;
    cin >> u >> v >> w;
    adj[u].push_back({w,v});
  }

  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
  d[st] = 0;
  // 우선순위 큐에 (0, 시작점) 추가
  pq.push({d[st],st});
  while(!pq.empty()){
    auto cur = pq.top(); pq.pop(); // {비용, 정점 번호}
    // 거리가 d에 있는 값과 다를 경우 넘어감
    if(d[cur.Y] != cur.X) continue;
    for(auto nxt : adj[cur.Y]){
      if(d[nxt.Y] <= d[cur.Y]+nxt.X) continue;
      // cur를 거쳐가는 것이 더 작은 값을 가질 경우
      // d[nxt.Y]을 갱신하고 우선순위 큐에 (거리, nxt.Y)를 추가
      d[nxt.Y]= d[cur.Y]+nxt.X;
      pq.push({d[nxt.Y],nxt.Y});
    }
  }

  for(int i= 1; i <= v; i++){
    if(d[i]= INF) cout << "INF\n";
    else cout << d[i] << "\n";
  }
}

0x02 경로 복원 방법

BOJ 11779: 최소 경로 구하기 2

문제 풀이

Note_

리뷰

출처: 바킹독님의 실전알고리즘 강의