[C++] 다익스트라 알고리즘

그래프 알고리즘에서 '최소 비용', '최단 거리'를 구해야 하는 경우,

사용할 수 있는 대표적인 알고리즘으로는

'다익스트라 알고리즘', '벨만-포드 알고리즘', '플로이드 워샬 알고리즘'이 있다.

 

이번 글에서는 '다익스트라 알고리즘'에 대해서 알아보겠다.

 

1. 언제 쓰이나요?

다익스트라 알고리즘은 '최소 비용' 중에서도,

주어진 두 노드(시작 노드, 도착 노드)사이의 최소 비용인 '경로'를 찾을 때 유용하게 사용된다.

가중치의 값이 모두 양수일 때(즉, 가중치에 음수가 없을 때) 사용된다.

 

하다보면 '당장 눈 앞에 드는 비용이 더 적다고, 해당 정점을 다시는 안쳐다봐도 될까?' 이런 질문이 생길 수 있다.

하지만 가중치 값이 양수이기만 하면 이는 만족하므로 걱정하지 않아도 된다.

 

2. 동작 원리

2-1.O(N^2) 반복문을 통한 시간 복잡도

지금부터 '비용' 이라는 말을 많이 사용하게 될 것이다. 이 '비용' 값은 1차원 배열 Dist[] 배열에 저장되어 있다고 생각하자.

 

0.초기 Dist[] 배열 모든 값은, 무한대(INF)로 초기화 되어있다.

1.시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.

2.방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로 선택해준다.

3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.

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

 

1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.

//시작 노드-연결된 i노드의 가격을 Dist 배열에 업데이트
for (int i=1; i <= V; i++) Dist[i] = MAP[Start][i];
Dist[Start]=0; //시작 노드에서의 비용은 0으로 바뀐다.
Select[Start]=true;

 

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;
        //현재 제일 작은 값보다, Dist[i] 비용이 더 작으면, Dist[i] 비용을 최솟값으로 선택
        if (Dist[i] < Min_Dist)
        {
        	Min_Dist = Dist[i];
            Min_Idx = i;
        }
    }
    return Min_Idx;
}

 

3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.

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

 

4.2-3번 과정을 반복한다.

몇 번 반복해야하는지 판단해야한다.

1번 정점에서 -> 3번 정점 선택하고 업데이트 1번 2번 정점 선택 -> 업데이트 ... 6번 정점 선택 -> 종료!(업데이트 없음)

 

즉 업데이트는 N(정점의 수)-1번 진행한다.

 

[전체 코드]

//다음 노드 선택
int Find_Shortest_Node()
{
	int Min_Dist, Min_Idx;
    Min_Dist = INF;
    Min_Idx = -1;
    
    for (int i=1; i <=V; i++) //V는 정점의 수
    {
    	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);
    }
}

 

2-2. 우선순위 큐를 이용한 방법 O(E*logN) E=간선 수, N=노드 수

인접한 간선들을 모두 Queue에 집어 넣은 후, 최소힙을 구하는 연산을 통ㅎ서, 최소비용이 드는 정점부터 처리하는 방식이다.

시간복잡도가 O(E*logN)인 이유는

-모든 정점들에 대해서 최소힙으로 추출하는데 걸리는 시간복잡도가 O(logN)이다.

-각 노드마다 인접한 모든 간선들을 확인해봐야하므로 시간복잡도가 O(E)이다.

 

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

 

아래와 같이 선언하면, 값이 작을 수록 우선순위를 갖는 최소힙으로 사용이 가능하다.

priority_queue<int, vector<int>, greater<int>> PQ;

 

[출처]

개인적으로 공부를 위하여, 아래 블로그 내용을 상세하게 참고한 글이다.

https://yabmoons.tistory.com/364