[C++/최단경로] 1. Dijkstra 다익스트라

그래프 알고리즘 '최소 비용' 대표 알고리즘
1. 다익스트라 알고리즘
2. 벨만- 포드 알고리즘
3. 플로이드 워샬 알고리즘

 

 

다익스트라 알고리즘

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

 

다익스트라 알고리즘의 동작 원리

1차원 배열인 Dist[]라는 배열에 '비용' 들이 저장되어 있다. 

초기 Dist 배열의 모든 값은 무한대(INF)로 초기화 한다. 

 

[동작 순서]

1. 시작 노드와 연결된 모든 정점들의 거리를 비교해서 업데이트 한다. 시작 노드를 방문 노드로 체크
2. 방문하지 않은 정점 중, 비용이 가장 적게 드는 정점을 선택한다. 해당 정점의 방문 노드 체크
3. 2번 과정에서 갱신될 수 있는 정점들의 거리를 갱신시켜준다. 
4. 2~3 반복

 

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

위와 같이 생긴 그래프가 있다고 하고, 시작노드를 1번으로 가정한다. 

1번 노드와 인접한 정점 : 2번, 3번

 

visitied[1] = true;

아래 표를 Dist[]라고 했을 때 다음과 같이 갱신 된다. (동작 원리 1번) 

1	2	3	4	5	6
0 (시작노드)	4	2	INF	INF	INF

 

2. 방문하지 않은 정점 중, 비용이 가장 적게 드는 정점을 선택한다. 해당 정점의 방문 노드 체크

Dist[] 표를 보면 3번 정점이 해당된다.

 

3번 노드를 선택!

visited[3] = true;

 

 

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

Dist[5] = Dist[3] + Dist[3]->Dist[5]

1	2	3	4	5	6
0 (시작노드)	4	2	INF	6	INF

 

다음은 2번 노드가 가장 가까움! 

 

이 과정을 모든 노드에 방문할 때 까지 진행한다!

 

다익 스트라 알고리즘 구현

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

for(int i=1; i<=V; i++) Dist[i] = MAP[Start][i];
Dist[Start] = 0;
visited[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 (visited[i] == true) continue;
		if (Dist[i] < Min_Dist) {
			Min_Dist = Dist[i];
			Min_Idx = i;
		}
	}

	return Min_Idx;

}

 

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

void Update_Dist(int NewNode) {
	// NewNode : 2번에서 선택한 정점 
	for (int i = 1; i <= V; i++) {
		if (visited[i]) continue;
		if (Dist[i] > Dist[NewNode] + MAP[NewNode][i]) {
			Dist[i] = Dist[NewNode] + MAP[NewNode][i];
		}
	}
}

 

계속 반복해주면 된다. 

 

#include<iostream>
#include<algorithm>

using namespace std;

#define INF 1e9;

int V = 6;

int visited[6];
int Dist[6];

int MAP[6][6];

int Find_Shortest_Node() {
	int Min_Dist, Min_Idx;
	Min_Dist = INF;
	Min_Idx = -1;

	for (int i = 1;i <= V;i++) {
		if (visited[i] == true) continue;
		if (Dist[i] < Min_Dist) {
			Min_Dist = Dist[i];
			Min_Idx = i;
		}
	}

	return Min_Idx;

}

void Update_Dist(int NewNode) {
	// NewNode : 2번에서 선택한 정점 
	for (int i = 1; i <= V; i++) {
		if (visited[i]) continue;
		if (Dist[i] > Dist[NewNode] + MAP[NewNode][i]) {
			Dist[i] = Dist[NewNode] + MAP[NewNode][i];
		}
	}
}

int Dijkstra() {
	int Start = 1;
	for (int i = 1; i <= V; i++) Dist[i] = MAP[Start][i];
	Dist[Start] = 0;
	visited[Start] = 1;

	for (int i = 0; i < V - 1;i++) {
		int NewNode = Find_Shortest_Node();

		visited[NewNode] = 1;
		Update_Dist(NewNode);
	}
}

 

다익스트라 (우선순위 큐,  priority_queue)

C++에서 다익스트라를 구현하는 방법은 하나 더 존재하는데, 바로 우선순위 큐를 사용하는 것이다.

 

우선순위 큐로 구현할 때는 visited 배열이 필요없다. 또, find_shortest_node 함수도 필요없다! 

 

우선순위 큐 다익스트라의 동작과정

1. Dist 배열을 전부 INF로 초기화하고 노드 정보 입력
2. Dist[Start] = 0
3. priority_queue에 {0, 목적지노드} 를 push한다. // 
4. Dist[노드] < 비용 이면 skip -> 이미 노드까지의 최소비용을 알고 있다는 뜻. 
5. 노드의 모든 인접 노드를 검사하고 비용을 갱신, pq에 {갱신 비용, 인접노드} 를 push한다. 
6. 4,5를 계속 반복한다. !q.empty()

 

3. priority_queue에 {0, 목적지노드} 를 push한다.

priority_queue {0,1}

 

4. Dist[노드] < 비용 이면 skip -> 이미 노드까지의 최소비용을 알고 있다는 뜻. 

5. 노드의 모든 인접 노드를 검사하고 비용을 갱신, pq에 {갱신 비용, 인접노드} 를 push한다. 

 

priority_queue {2,3} {4,2} 

 

다시 pq.top()을 불러오고 weight = 2, node = 3를 저장해 준 후 Dist[3]=2

 

3~5번을 반복하면

priority_queue {4,2} {6,5}

priority_queue {6,5} {8,4} {9,5} 

....

 

의 방식으로 Dist를 모두 가질 때 까지 반복한다. 

 

이 때, pop()해주는 과정에서 Dist[i]가 있으면 넘어가야하는데 

priority_queue {6,5} {8,4} {9,5} 처럼 같은 노드가 queue에 쌓일 수 있기 때문이다. 

 

이때, queue에 넣을때 가중치에 - 처리를 해줘야 한다.  >> 우선순위 큐의 디폴트가 내림차순이기 때문에!!!!!

void Dijkstra_Using_Heap(){
  priority_queue<pair<int,int>> pq;
  pq.push({0, start})
  Dist[start] = 0;
  
  whiile(!pq.empty()){
    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({-Dist[Next], Next});
      }
    }
  }
  for(int i=1; i<=V; i++){
    if(Dist[i] == INF) cout<< "INF" << "\n";
    else cout << Dist[i] << '\n';
  }

}

 

 

[관련 문제]

1753번: 최단경로

 

[참고한 블로그]

 

[ 다익스트라 알고리즘 ] 개념과 구현방법 (C++)