[알고리즘/그래프] 다익스트라 (Dijkstra)

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

 

가중치가 있는 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘

단, 모든 간선의 가중치는 0 이상의 양수여야 한다.

(음수 가중치가 있으면 벨만-포드 알고리즘을 사용)

---

입력: 정점 V개, 간선 E개, 가중치가 양수인 그래프
목표: 시작 정점 start로부터 모든 정점까지의 최소 비용(거리)

 

우선순위 큐 (priority_queue)를 현재까지 가장 짧은 거리의 정점을 빠르게 찾기 위해 사용

거리 배열 (distance[])은 각 정점까지의 최단 거리 저장

---

동작

 

1. 시작 정점의 거리는 0으로 설정, 나머지는 무한대(INF)
2. 시작 정점을 우선순위 큐에 넣음
3. 큐에서 현재 가장 가까운 정점을 꺼냄
4. 해당 정점의 이웃들을 확인하면서 거리 배열을 업데이트
5. 갱신된 정점은 다시 우선순위 큐에 넣음
6. 큐가 빌 때까지 반복

 

---

코드 

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

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

struct Edge
{
    int to;
    int weight;
};

std::vector<int> dijkstra(int start, int numVertices, const std::vector<std::vector<Edge>>& graph)
{
    std::vector<int> distance(numVertices + 1, INF);
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;

    distance[start] = 0;
    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 (const Edge& edge : graph[currentNode])
        {
            int next = edge.to;
            int nextDist = currentDist + edge.weight;

            if (nextDist < distance[next])
            {
                distance[next] = nextDist;
                pq.push({nextDist, next});
            }
        }
    }

    return distance;
}

int main()
{
    int numVertices, numEdges;
    std::cin >> numVertices >> numEdges;

    std::vector<std::vector<Edge>> graph(numVertices + 1);

    for (int i = 0; i < numEdges; ++i)
    {
        int from, to, weight;
        std::cin >> from >> to >> weight;
        graph[from].push_back({to, weight});
    }

    int start;
    std::cin >> start;

    std::vector<int> result = dijkstra(start, numVertices, graph);

    for (int i = 1; i <= numVertices; ++i)
    {
        if (result[i] == INF)
        {
            std::cout << "INF\n";
        }
        else
        {
            std::cout << result[i] << '\n';
        }
    }

    return 0;
}