(c++)다익스트라 알고리즘 - 1753번 : 최단경로

 

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

1753번: 최단경로

 

---

 

다익스트라 알고리즘

 

 

유향 그래프에서 가중치가 적용된다면 가중치를 가장 적게 하는 결과를 내는 알고리즘이다.

 

출발점으로 하나의 노드를 선택하여

 

배열의 초기값으로 선택된 노드에서 이어져 있는 노드에 대한 가중치를 넣어준다. (자기 자신은 0으로 한다.)

 

해당 노드로 바로 갈 수 있는 간선이 존재하지 않는다면 INF 즉 최댓값으로 둔다.

 

초기 배열이 완성된다면 자기 자신을 제외하고 가장 최솟값의 노드를 선택한다.

 

최솟값의 노드에서 바로 갈 수 있는 모든 노드에 대해서 거리를 비교한다.

 

 ex ) d[B] = min(d[B] , d[C][B])) 

 

만일 출발 노드가 A이고, 노드 C가 최솟값이였을 경우 C에서 바로 갈 수 있는 노드가 B라고 한다면

 

배열에 저장되어있는 A - B의 거리와 A - C - B로 가는 거리를 비교하여 가장 작은 값을 저장하고 동결한다.

 

위 가정을 반복하여 출발 노드를 제외한 모든 노드들의 최솟값을 비교하여 동결하여 결과를 낸다.

 

---

 

1753번 : 최단경로

 

해당 문제는 일반적인 다익스트라 알고리즘을 적용하면 풀 수 없다.

 

기본적으로 다중 그래프가 아닐 경우에 대해서 알고리즘이 되어있어

 

추가적으로 가장 작은 간선을 선택하여 알고리즘을 적용시키거나 

 

우선순위 큐를 사용하는 개선된 다익스트라 알고리즘을 적용하면 된다.

 

우선순위 큐는 원소들에 대한 우선순위를 부여해 원소를 뺄 때 우선순위가 높은 원소부터 빼내는 것이다.

 

우선순위 큐를 사용한다면 모든 노드를 순회해야 하는 비용을 줄일 수 있다.

 

다익스트라 기본 = O(V ^ 2)

다익스트라 : 우선순위 큐 = O((V + E))log V)

V : 정점의 수, E : 간선의 수

 

원래는 방문 처리를 통해서 구현하지만

 

우선순위 큐는 방문처리하지 않는다.

 

 

#include<bits/stdc++.h>
#define INF 1e9

using namespace std;

// 노드 수 n, 간선 수 m, 시작 노드
int n, m, start; 
// 노드 정보 동적 배열
vector<pair<int, int> > graph[20001];
// 최단거리 테이블
int d[20001];

// 다익스트라 알고리즘
void dijkstra(int start) {
  priority_queue<pair<int, int> > pq;
  pq.push({0, start});
  d[start] = 0;

  while (!pq.empty()) {
    int dist = -pq.top().first; // 최대 힙으로 되어있어 부호 -
    int now = pq.top().second;
    pq.pop();
    if (d[now] < dist) continue;
    for (int i = 0; i < graph[now].size(); i++) {
      int cost = dist + graph[now][i].second;
      if (cost < d[graph[now][i].first]) {
        d[graph[now][i].first] = cost;
        // 최대 힙이라 부호 반대
        pq.push(make_pair(-cost, graph[now][i].first)); 
      }
    }
  }
}

int main(void) {
  cin >> n >> m;
  cin >> start;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({b, c});
  }
  fill_n(d, 20001, INF);
  dijkstra(start);

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