다익스트라

한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘

• 가중치가 있는 그래프에서 사용한다.
• 음수 가중치를 가진 간선이 있을 땐 사용할 수 없다.
• 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다. (Greedy)
• 해당 노드로부터 갈 수 있는 노드들을 갱신한다. (DP)

1. 최단 거리를 계속 갱신하면서, 가장 가까운 정점부터 방문
2. 이미 방문한 노드는 다시 방문하지 않음
3. 우선순위 큐를 활용해 효율적으로 구현 가능

우선순위 큐를 활용한 다익스트라 구현

vector<pair<int,int>> graph[N]; // 도착 - 가중치 정보를 담은 그래프
vector<int> DP(N,INT_MAX); // 시작점 s 로부터의 최단 거리를 담은 배열 

void dijkstra(int s)
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0,s});
    DP[s] = 0;
    
    while(pq.size())
    {
        int cnt = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        
        for(int i = 0; i < graph[cur].size(); ++i)
        {
            int next = graph[cur][i].first;
            int weight = graph[cur][i].second;
            
            if(DP[next] > cnt + weight)
            {
                DP[next] = cnt + weight;
                pq.push({DP[next],next});
            }
        }
    }
}

시간 복잡도는 O((V+E)log V) 로 V 는 정점의 개수, E 는 간선의 개수이다.