(1753) 최단경로

https://www.acmicpc.net/problem/1753

단계별로 풀어보기

29단계(최단 경로) 1번째

 

 

 

이제부터 그래프에 가중치가 생긴다. 그 중 가장 기본적인 다익스트라 알고리즘이다.

다익스트라 알고리즘은 일종의 그리디 알고리즘이다. 음수 가중치가 없으므로 매 순간 최단 거리를 탐색하면 모든 최단거리를 찾을 수 있다.

또한 옛날 다익스트라 알고리즘은 거리 배열과 별개로 방문 배열을 만들어 체크하는 경우도 있는데, 큐에서 꺼낸 현재 원소의 거리가 방문 배열에서 현재 원소 노드의 거리보다 클 때 스킵하는 조건을 추가하면 방문 배열과 같은 효과를 낼 수 있다.

 

[추가내용] 이 코드에서도 쓰는, 중복 정점을 허용하는 우선순위 큐 방식은 실제로 그리디 알고리즘보다 가지치기를 빡빡하게 하는 백트래킹에 가까운, 음수 간선이 있어도 쓸 수 있는 방식이라고 한다. (인터넷에서 나오는 대부분의 다익스트라 알고리즘은 설명은 그리디 알고리즘 방식처럼 하면서도 실제로는 이 방식의 코드인 경우가 많다.) 다만 데이터가 일반적이지 않고 극단적인 경우 최악의 시간복잡도가 매우 크기 때문에 PS에서 사용하기에는 어렵다고 한다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;
#define INF 200001
typedef pair<int,int> p;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int v, e, k;
  
  cin >> v >> e >> k;
  
  priority_queue<p, vector<p>, greater<p>> pq;
  vector adj(v+1, vector<p>());
  vector<int> dist(v+1, INF);
  
  while(e--){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    adj[a].push_back({c, b});
  }
  
  dist[k]= 0;
  pq.push({0, k});
  
  while(!pq.empty()){
    p now= pq.top();
    pq.pop();
    
    // 이 조건문이 방문 배열과 같은 효과를 낸다
    if(now.first>dist[now.second])  continue;
    
    for(p next:adj[now.second]){
      if(now.first+next.first<dist[next.second]){
        dist[next.second]= now.first+next.first;
        pq.push({now.first+next.first, next.second});
      }
    }
  }
  
  for(int i=1;i<=v;i++){
    if(dist[i]==INF)  cout << "INF\n";
    else  cout << dist[i] << "\n";
  }
  
  return 0;
}