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

그래프 알고리즘에서 최소 비용을 구하는 문제에서 사용하는 대표적인 알고리즘이다. 두 노드 사이의 비용을 구하는 문제에 유용하게 사용된다.

구조

1. 시작 노드와 직접적으로 연결된 정점들의 비용을 비교하여 업데이트하고 시작 노드를 방문한 노드로 체크한다.

• 시작 노드와 직접적으로 연결된 정점들의 비용을 업데이트해준다.
• 시작 노드를 방문한 노드로 체크하면 이후로는 방문한 노드의 최소비용을 업데이트하지 않겠다는 의미를 가진다.

2. 방문한 정점들과 연결된 정점들 중 가장 비용이 적게 드는 정점을 선택하고, 그 정점을 방문한 노드로 체크한다.

• 이전에 설정된 비용과 새로 비교할 수 있는 비용을 비교하여 더 작은 비용을 그 노드이 최소비용으로 업데이트 해준다.

3. 2번 과정에 의해 업데이트 될 수 있는 정점들의 비용을 업데이트해준다.

• 방문한 노드에 새로운 정점이 추가되었으므로 새로 추가된 방문한 노드와 직접적으로 연결된 정점들에 대한 비용을 업데이트 해준다.

4. 2,3번 과정을 반복한다.

한계

비용이 적은 정점을 방문한 노드로 체크하고 그 노드에 대한 비용을 수정하지 않게 되는데 이는 모든 비용이 양수라는 가정 하에 이뤄지는 것이다. 즉, 모든 비용이 양수일 때만 다익스트라 알고리즘을 적용시킬 수 있다.

Code

int Find_Shortest_Node()
{
    int Min_Dist, Min_Idx;
    Min_Dist = INF;
    Min_Idx = -1;
 
    for (int i = 1; i <= V; i++)
    {
        if (Select[i] == true) continue;
        if (Dist[i] < Min_Dist)
        {
            Min_Dist = Dist[i];
            Min_Idx = i;
        }
    }
    return Min_Idx;
}
 
void Update_Dist(int NewNode)
{
    for (int i = 1; i <= V; i++)
    {
        if (Select[i] == true) continue;
        if (Dist[i] > Dist[NewNode] + MAP[NewNode][i])
        {
            Dist[i] = Dist[NewNode] + MAP[NewNode][i];
        }
    }
}
 
void Dijkstra()
{
    for (int i = 1; i <= V; i++) Dist[i] = MAP[Start][i];
    Dist[Start] = 0;
    Select[Start] = true;
    
    for (int i = 0; i < V - 1; i++)
    {
        int NewNode = Find_Shortest_Node();
 
        Select[NewNode] = true;
        Update_Dist(NewNode);
    }
}

• 힙을 이용하는 우선순위 큐는 시간을 줄일 수 있다.

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;
    }
}