[C++로 배우는 알고리즘과 자료구조] Day 25: 다익스트라 알고리즘 (Dijkstra's Algorithm)

다익스트라 알고리즘 (Dijkstra's Algorithm)

다익스트라 알고리즘은 가중치가 있는 그래프에서 단일 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음수 가중치가 없는 그래프에서 작동합니다.

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

• 일반적인 구현: (O(V^2))
• 우선순위 큐를 사용한 구현 (힙): (O((V + E) \log V))

다익스트라 알고리즘 구현

그래프 구현 (인접 리스트 사용)

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>

// 그래프 클래스 정의
class Graph {
public:
    Graph(int vertices);
    void addEdge(int u, int v, int weight); // 간선 추가
    void dijkstra(int src); // 다익스트라 알고리즘 호출

private:
    int vertices; // 정점의 수
    std::vector<std::list<std::pair<int, int>>> adjList; // 인접 리스트
};

// 그래프 생성자 정의
Graph::Graph(int vertices) {
    this->vertices = vertices;
    adjList.resize(vertices);
}

// 간선 추가 함수 정의
void Graph::addEdge(int u, int v, int weight) {
    adjList[u].push_back(std::make_pair(v, weight));
    adjList[v].push_back(std::make_pair(u, weight)); // 무방향 그래프
}

// 다익스트라 알고리즘 함수 정의
void Graph::dijkstra(int src) {
    // 최소 힙 (우선순위 큐)
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    std::vector<int> dist(vertices, INT_MAX); // 모든 정점의 거리를 무한대로 초기화

    // 시작 정점의 거리를 0으로 설정하고 우선순위 큐에 삽입
    pq.push(std::make_pair(0, src));
    dist[src] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        // 인접 정점과 가중치를 탐색
        for (auto x : adjList[u]) {
            int v = x.first;
            int weight = x.second;

            // 더 짧은 경로를 찾은 경우
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push(std::make_pair(dist[v], v));
            }
        }
    }

    // 최단 경로 출력
    std::cout << "정점 " << src << "로부터의 최단 거리:" << std::endl;
    for (int i = 0; i < vertices; ++i) {
        std::cout << "정점 " << i << ": " << dist[i] << std::endl;
    }
}

// 메인 함수
int main() {
    Graph g(9);
    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);

    g.dijkstra(0);

    return 0;
}

 

설명

1. 그래프 클래스:
   • vertices: 그래프의 정점 수.
   • adjList: 각 정점의 인접 리스트를 저장하는 벡터.
2. addEdge 함수:
   • 정점 u에서 정점 v로의 간선과 가중치를 그래프에 추가합니다. 무방향 그래프이므로 반대 방향의 간선도 추가합니다.
3. dijkstra 함수:
   • 주어진 시작 정점에서 다익스트라 알고리즘을 수행합니다.
   • 최소 힙(우선순위 큐)을 사용하여 최단 거리를 효율적으로 찾습니다.
   • 시작 정점의 거리를 0으로 설정하고, 모든 정점의 거리를 무한대로 초기화합니다.
   • 인접 정점을 탐색하여 더 짧은 경로를 찾으면 거리를 업데이트하고 우선순위 큐에 삽입합니다.

다익스트라 알고리즘의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 알고리즘과 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 26: 플로이드-워셜 알고리즘"에 대해 학습하겠습니다.