📒Dijkstra Algorithm

✍Dijkstra Algorithm이란?

DP를 사용한 한 노드에서 다른 나머지의 노드에 대한 최단경로 탐색 알고리즘.
단, 음의 경로가 있다면 사용할 수 없다.

✍특징

📌특징

• 어떠한 경우에도 음의 경로가 존재하면 안된다.
• 기존에 구한 경로에 대한 가중치 값을 사용하기 때문에 DP이다.

📌과정

1. 출발 노드를 설정한다.
2. 출발 노드를 기준으로 최소값을 모두 최신화한다.
3. 방문하지 않은 정점 중 가장 최소값의 가중치를 가지는 정점을 방문한다.
4. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다.

📌구현

void Dijkstra_Using_Heap()
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, Start));
    Dist[Start] = 0;
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < Vertex[Cur].size(); i++)
        {
            int Next = Vertex[Cur][i].first;
            int nCost = Vertex[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
 
    for (int i = 1; i <= V; i++)
    {
        if (Dist[i] == INF) cout << "INF" << endl;
        else cout << Dist[i] << endl;
    }
}

출처: https://yabmoons.tistory.com/364 [얍문's Coding World..]

📌관련 문제

1. 프로그래머스-배달