dijkstra

다익스트라 알고리즘

하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 방법

시간 복잡도는 O(E log_2(V))

초기화

1. 거리배열 costs를 전부 INF로 초기화한다.
2. 시작점의 거리를 0으로 지정한다 (A -> A 의 거리는 0이다)
3. 우선순위 큐 pq를 선언한다. (cost에 최소값이 제일 위에 올라와야함)
4. pq에 시작점을 저장한다.

while문 (pq가 빌 때까지)

1. 현재 노드에 pq의 top값을 할당하고 pop
2. 현재 노드에 연결된 간선을 탐색한다.
3. 간선의 도착점까지 cost를 비교한다 (현재 노드를 지나서 가는 경우 cost vs 원래 간선까지의 cost)
4. 현재 노드를 지나가는 경우의 가중치 합계가 더 작으면
   1. cost를 갱신한다 (costs 배열의 그것을 갱신한다)
   2. pq에 {cost, 도착점}을 push한다.

struct Edge {
  int to, cost;

  bool operator<(const Edge &b) const {
    return cost > b.cost; // 우선순위 큐의 top이 최소값이 되도록
  }
};

vector<vector<Edge>> graph;
vector<int> costs; // 처음에 INFINITY로 초기화해야함

void dijkstra(int start, vector<vector<Edge>> &graph, vector<int> &costs) {
  priority_queue<Edge> pq;

  fill(costs.begin(), costs.end(), INFINITY);

  pq.push({0, start, 0});
  while (!pq.empty()) {
    Edge cur = pq.top();
    pq.pop();

    for (Edge next : graph[cur.to]) {
      int new_val = costs[cur.to] + next.cost;
      int before_val = costs[next.to];

      if (new_val < before_val) {
        costs[next.to] = new_val;
        pq.push({next.to, new_val});
      }
    }
  }
}

pq를 최소 힙으로 구현하는 방법

priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > pq;

// 아래 header를 추가해서 compare함수를 만들 수 있다.
#include <functional>	// to use greater<>
greater<> // compare