[그래프] 다익스트라 / Dijkstra's algorithm

2024. 10. 3. 07:42🐣/Algorithm

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

다익스트라 알고리즘 / Dijkstra's algorithm

다익스트라 알고리즘은 단일 출발점 최단 경로를 찾는 알고리즘입니다. 가중치가 음수가 아닌 그래프에서 출발점에서 모든 다른 정점까지의 최단 경로를 구할 때 사용됩니다. 다익스트라 알고리즘은 우선순위 큐(Priority Queue)를 이용해 최단 거리가 가장 작은 정점을 빠르게 탐색하여 최적화된 성능을 제공합니다.

다익스트라 알고리즘의 특징

  1. 음의 가중치 간선 허용 안 함: 음의 가중치가 있는 그래프에서는 올바르게 작동하지 않습니다.
  2. 우선순위 큐 사용: 최단 경로를 더 효율적으로 찾기 위해, 가중치가 가장 작은 정점을 빠르게 선택하기 위해 우선순위 큐(최소 힙)을 사용합니다.
  3. 시간 복잡도: O((V + E) * log V) - 여기서 V는 정점의 수, E는 간선의 수입니다. 우선순위 큐를 사용하는 경우, 힙 연산이 log V 시간에 수행되기 때문에 매우 효율적입니다.

다익스트라 알고리즘의 동작 원리

  1. 초기화: 출발 정점의 거리를 0으로 설정하고, 나머지 정점들의 거리는 무한대로 초기화합니다.
  2. 우선순위 큐 사용: 거리가 최소인 정점을 큐에서 꺼내고, 이 정점과 연결된 모든 간선을 탐색하여 인접한 정점의 최단 거리를 업데이트합니다.
  3. 반복: 모든 정점에 대해 위의 과정을 반복합니다. 정점의 최단 거리가 갱신될 때마다 우선순위 큐에 삽입하여 다음으로 최단 거리가 작은 정점을 선택합니다.

다익스트라 알고리즘의 C++ 구현

아래는 C++에서 우선순위 큐를 사용하여 다익스트라 알고리즘을 구현한 코드입니다. 이 코드는 특정 출발지에서 모든 다른 정점까지의 최단 거리를 구하는 방식으로 동작합니다.

코드예시 BOJ 18352 특정 거리의 도시 찾기

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9; // 무한대 값 (충분히 큰 값)

vector<int> dijkstra(int n, int start, vector<vector<pair<int, int>>>& graph) {
    vector<int> distance(n + 1, INF);  // 최단 거리 배열 초기화
    distance[start] = 0;

    // 우선순위 큐 선언 (pair<int, int>: (거리, 정점))
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});  // (거리, 정점) 순서로 삽입

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

        // 현재 노드의 최단 거리가 이미 처리된 거리보다 크다면 무시
        if (currentDist > distance[currentNode]) {
            continue;
        }

        // 현재 노드에 연결된 다른 노드들을 확인
        for (auto& edge : graph[currentNode]) {
            int nextNode = edge.first;
            int weight = edge.second;
            int newDist = currentDist + weight;

            // 더 짧은 경로를 발견한 경우 업데이트
            if (newDist < distance[nextNode]) {
                distance[nextNode] = newDist;
                pq.push({newDist, nextNode});
            }
        }
    }

    return distance;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k, x;
    cin >> n >> m >> k >> x;

    // 인접 리스트로 그래프 표현 (pair<int, int>: (도착 노드, 가중치))
    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back({b, 1});  // 모든 간선의 가중치는 1로 설정
    }

    // 다익스트라 알고리즘 실행
    vector<int> distance = dijkstra(n, x, graph);

    // 최단 거리가 정확히 k인 도시 찾기
    vector<int> result;
    for (int i = 1; i <= n; i++) {
        if (distance[i] == k) {
            result.push_back(i);
        }
    }

    // 결과 출력
    if (result.empty()) {
        cout << "-1\n";
    } else {
        sort(result.begin(), result.end());
        for (int city : result) {
            cout << city << "\n";
        }
    }

    return 0;
}

코드 설명

  1. 그래프 표현:
    • 그래프는 인접 리스트 형태로 표현됩니다. graph[i]는 정점 i와 연결된 모든 간선을 (도착 정점, 가중치) 형태로 저장합니다.
    • 입력을 받아서 간선을 추가할 때, 모든 간선의 가중치를 1로 설정했습니다 (graph[a].push_back({b, 1})).
  2. 다익스트라 알고리즘 (dijkstra 함수):
    • 최단 거리 배열: distance 배열은 출발점에서 각 정점까지의 최단 거리를 저장합니다. 모든 값을 초기화한 후 출발점의 거리를 0으로 설정합니다.
    • 우선순위 큐 사용: 최소 힙을 사용하기 위해 priority_queue를 사용하며, greater<pair<int, int>>를 지정하여 최소 거리가 먼저 나오는 우선순위 큐를 만듭니다.
    • 정점 처리: 큐에서 거리가 가장 짧은 정점을 꺼내고, 그 정점과 연결된 간선을 따라 다른 정점의 최단 거리를 갱신합니다. 최단 거리가 갱신될 때마다 큐에 새로 넣습니다.
  3. 결과 출력:
    • 최단 거리가 K인 도시들을 result 벡터에 모아 오름차순으로 출력합니다.
    • 결과가 없을 경우 -1을 출력합니다.

다익스트라 알고리즘의 시간 복잡도

  • 시간 복잡도: O((V + E) * log V).
    • V는 정점의 수 (n), E는 간선의 수 (m)입니다.
    • log V는 우선순위 큐(힙)에서 삽입하거나 삭제할 때 소요되는 시간입니다.
    • 따라서, 그래프의 모든 정점과 간선을 탐색하며 우선순위 큐에서 정점 선택을 효율적으로 하기 위해 로그 시간이 더해집니다.

다익스트라 알고리즘과 BFS의 차이점

  1. 가중치:
    • BFS는 모든 간선의 가중치가 같을 때(예: 모든 간선의 가중치가 1인 경우) 효율적으로 사용할 수 있습니다.
    • 다익스트라 알고리즘은 가중치가 다를 때, 최단 거리를 찾기 위해 사용합니다.
  2. 우선순위 큐 사용:
    • 다익스트라는 우선순위 큐를 사용하여 현재 방문 가능한 정점 중 가장 비용이 적은 정점을 먼저 탐색합니다.
    • BFS는 를 사용하여 정점들을 동일한 거리 순서로 탐색합니다.

결론

  • 다익스트라 알고리즘은 가중치가 양수일 때 최단 거리를 찾는 데 매우 효율적입니다.
  • 이 알고리즘은 최소 힙을 이용해 정점 선택을 최적화하여 시간 복잡도를 줄입니다.
  • 이 문제에서 BFS도 적합하지만, 다익스트라 알고리즘을 사용하면 더 범용적이고 복잡한 문제(예: 가중치가 다양한 경우)에도 적용할 수 있습니다.

 

다익스트라 문제 추천

기본 - 5972 택배 배송
응용 - 17396 백도어