다익스트라 알고리즘

다익스트라 알고리즘은 특정 정점에서 다른 정점으로가는 최단 경로를 구합니다.

여기서 DP가 적용이 됩니다. DP는 이미 최단경로를 구한 곳은 다시 구할 필요가 없기 때문입니다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할때 최단경로를 구할 수 있습니다. 우선순위 큐를 사용하여 구현하였습니다.

 

void dijkstra(vector<vector<int>> matrix, int start){//인접 행렬임
    vector<int> distance(matrix.size(), INT_MAX);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    pq.emplace(0,start);
    distance[start] = 0;

    while(!pq.empty()){
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if(cost > distance[cur])continue;

        for(int i = 0; i < matrix.size(); i++){
            int next_cost = cost + matrix[cur][i];
            if(matrix[cur][i] && distance[i] > next_cost){
                pq.emplace(next_cost,i);
                distance[i] = next_cost;
            }
        }
    }
}