Graph-다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘이란?

먼저 백번 글로 읽는 것 보다  움짤을 보자 

출처: 위키피디아

• 1. 다익스트라 알고리즘의 특징
  • 그래프 유형: 방향 그래프 또는 무방향 그래프에 적용 가능.
  • 가중치 조건: 간선 가중치(Weight)가 음수일 수 없음.
  • 출발점 기준: 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 계산.

  ---

  2. 알고리즘 동작 방식
  1. 초기화:
     • 출발점 s에서 모든 정점까지의 거리 값을 무한대(∞)로 설정.
     • 출발점 s의 거리는 0으로 설정.
     • 우선순위 큐(최소 힙)를 사용하여 가장 가까운 정점을 효율적으로 추출.
  2. 최단 거리 업데이트:
     • 현재까지 가장 짧은 경로로 방문하지 않은 정점을 선택.
     • 선택된 정점을 기준으로, 인접 정점의 거리 값을 업데이트.
     • 만약 새로운 경로가 기존 경로보다 짧다면, 해당 정점의 거리를 갱신.
  3. 반복:
     • 모든 정점이 처리될 때까지(또는 더 이상 최단 경로 갱신이 없을 때까지) 위 과정을 반복.

 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

void dijkstra(int n, int start, vector<vector<pair<int, int>>>& graph) {
    vector<int> dist(n, INF); // 최단 거리 배열
    dist[start] = 0;

    // 최소 힙 (거리, 노드 번호)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int currentDist = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();

        if (currentDist > dist[currentNode]) continue; // 이미 처리된 노드

        for (auto& neighbor : graph[currentNode]) {
            int nextNode = neighbor.first;
            int weight = neighbor.second;

            if (dist[currentNode] + weight < dist[nextNode]) {
                dist[nextNode] = dist[currentNode] + weight;
                pq.push({dist[nextNode], nextNode});
            }
        }
    }

    // 결과 출력
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            cout << "Node " << i << ": INF\n";
        } else {
            cout << "Node " << i << ": " << dist[i] << "\n";
        }
    }
}

int main() {
    int n = 5; // 정점 개수
    vector<vector<pair<int, int>>> graph(n);

    // 그래프 구성 (u → v, weight)
    graph[0].push_back({1, 1}); // A → B (1)
    graph[0].push_back({2, 4}); // A → C (4)
    graph[1].push_back({2, 2}); // B → C (2)
    graph[1].push_back({3, 6}); // B → D (6)
    graph[2].push_back({3, 3}); // C → D (3)
    graph[3].push_back({4, 1}); // D → E (1)

    int start = 0; // 시작 정점 (A)
    dijkstra(n, start, graph);

    return 0;
}