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

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

• 다이나믹 프로그래밍을 활용한 대표적인 최단 경로탐색 알고리즘
• 다익스트라 알고리즘은 특정 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌 (음의 간선은 포함 X)
• 다익스트라 알고리즘에서 최단 거리는 여러 개의 최단거리로 이루어져있기 때문에 작은 문제가 큰 문제의 부분 집합에 속해 있다고 할 수 있음
  • 따라서 다이나믹 프로그래밍 문제

작동 과정

1. 출발 노드 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용 저장
3. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택
4. 해당 노드를 거쳐서 특별한 노드로 가는 경우를 고려해 최소 비용 갱신
5. 3~4번 반복

 

0	2	5	1	무한	무한
2	0	3	2	무한	무한
5	3	0	3	1	5
1	2	3	0	1	무한
무한	무한	5	1	0	2
무한	무한	5	무한	2	0

                         (특정 행에서 열로 가는 비용)

 

노드 1을 선택하고 1과 연결된 세 개의 간선을 확인

 

0

2

5

1

무한

무한

1번 노드에서 다른 정점으로 가는 최소 비용은 다음과 같음. 배열을 만든 뒤에는 이 배열을 계속 갱신

현재 방문하지 않은 노드 중에서 가장 비용이 적은 노드는 4번. 따라서 4번 노드를 선택

 

기존에 5로 가는 최소 비용이 무한이었음. 그러나 4를 거쳐서 5로 가는 경우 비용 2 이므로 갱신

4를 거쳐서 3으로 가는 경우 비용이 4 이므로 기존보다 비용이 적음. 따라서 갱신

 

0

2

4

1

2

무한

다음으로 방문하지 않은 노드 중에서 가장 비용이 적은 노드는 2번

 

​

 

0

2

4

1

2

무한

2를 거쳐서 가더라도 비용이 갱신되는 경우가 없음.

​

다음으로 방문하지 않은 노드 중에서 가장 비용이 적은 노드는 5번

 

 

5를 거쳐서 3으로 가는 비용이 기존보다 적음. 따라서 갱신

또한 5를 거쳐서 6으로 가는 비용이 기존보다 적음. 따라서 이 또한 갱신

 

0

2

3

1

2

4

방문하지 않은 노드 중에서 가장 비용이 적은 노드 3 방문

 

​

갱신이 일어나지 않음.

 

0

2

3

1

2

4

마지막 노드 6 방문

 

결과 동일

 

0

2

3

1

2

4

                           (최종 배열)

​

코드

vector<pair<int, int>> a[7];//간선정보
int d[7];//최소 비용

void dijkstra(int start) {
	d[start] = 0;
	priority_queue<pair<int, int>> pq; //힙 구조
	pq.push(make_pair(0, start)); //가까운 순서대로 처리
	
	while (!pq.empty()) {
		int current = pq.top().second;
		int distance = -pq.top().first;//짧은 것이 먼저 오도록 음수화
		pq.pop(); 
		if (d[current] < distance) continue; //최단 거리가 아닌 경우 스킵
		for (int i = 0; i < a[current].size(); i++) {
			//선택된 노드의 인접 노드
			int next = a[current][i].second;
			int nextDistance = distance + a[current][i].first;

			if (nextDistance < d[next]) {
				d[next] = nextDistance;
				pq.push(make_pair(-nextDistance, next));
			}
		}
	}
}