현제 방문하지 않는 노드중에 최소 거리인 노드를 찾기 위해 최소 힙을 사용할 수 있습니다.

• 이때 시간복잡도는 O(ElogV)입니다.
• 5000개 이상의 노드가 있으면 느려지는 순차탐색에 비해 더 많은 노드를 빠르게 처리할 수 있습니다

의사코드

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

# define INF 99999999
// 시작 위치와 정점의 개수, 인접 행렬을 받아
// 최소 거리 행렬을 반환함
vector<int> dijkstra(int start, int N, vector<pair<int, int> > graph[]) {
  vector<int> dist(N, INF); // 거리를 저장할 리스트 초기화
  priority_queue<pair<int, int> > pq; // 우선순위 큐 선언

  dist[start] = 0; // 시작 노드 거리를 0으로 함
  pq.push({0, start});

  while (!pq.empty()) {
    int cur_dist = -pq.top().first; // 큐에서 꺼내 방문하고 있는 정점의 거리
    int cur_node = pq.top().second; // 정점의 인덱스(번호)
    pq.pop();

    for (int i = 0; i < graph[cur_node].size(); i++) {
      int nxt_node = graph[cur_node][i].first;
      int nxt_dist = cur_dist + graph[cur_node][i].second;

      if (nxt_dist < dist[nxt_node]){
        dist[nxt_node] = nxt_dist;
        pq.push({-nxt_dist, nxt_node});
      }
    }
  }
  return dist; 
}
int main() {
  const int N = 10;
  int E = 20;
  vector<pair<int, int> > graph[N]; // 그래프 형태 선언
  for (int i = 0; i < E; i++) {
    int from, to, cost; // 간선의 시작점, 끝점, 가중치
    cin >> from >> to >> cost;
    graph[from].push_back({to, cost});
    graph[to].push_back({from, cost});
  }
  vector<int> dist = dijkstra(0, N, graph);

  cout << "끝점까지의 최단거리" << dist[N - 1] << endl;

  return 0;
}

순차탐색과의 차이점?

순차탐색과 다르게 현제 위치에서 가장 짧은 거리에 있는 노드를 바로 찾아갈 수 있어 알고리즘 수행속도가 더 빠릅니다.