[자료구조 및 알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 알고리즘

 

다익스트라 알고리즘은 가중치가 양수만 존재하는 그래프에서 한 정점까지의 최단 경로를 구하는 알고리즘 중의 하나이다. 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복한다. 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다고 한다. 참고로, 그래프 알고리즘 중 최소 비용을 구하는 데는 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 등이 있다.

 

동작 단계

 

1. 출발 노드와 도착 노드를 설정한다.

2. 최단 거리 테이블을 초기화한다.

3. 현재 위치한 도드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 해당 노드를 방문처리한다.

4. 해당 노드를 거쳐 다른 노드로 넘어가는 가중치(간선 비용)을 계산해 최단 거리 테이블을 업데이트 한다.

5. 3~4의 과정을 반복한다.

 

요약하면

1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다.

2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다.

 

주의할 점

 

다익스트라 알고리즘은 음의 가중치가 있는 경우 사용할 수 없다. 음의 가중치가 있는 경우, 벨만-포드 알고리즘을 사용해야한다고 한다.

 

구현

 

하나씩 방문하는 방식으로 구현할 수도 있고, 우선순위 큐로 구현할 수도 있다.

 

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

 

시간복잡도: O(N^2)

 

우선순위 큐 이용

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

 

시간복잡도: O(E* logV) (E는 간선의 수, V는 정점의 수를 의미한다.)

코드 출처: https://yabmoons.tistory.com/364

 

파이썬 코드는 https://yganalyst.github.io/concept/algo_cc_book_7/ 에서 확인 가능하다.