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

다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변경한 형태이다. 다익스트라 알고리즘이 프림 알고리즘과 다른 두 가지 차이점은 다음과 같다.

 

• 프림 알고리즘은 경계로부터 최소 거리를 정점의 거리 값으로 설정하지만, 다익스트라 알고리즘은 시작 정점으로부터 각 정점까지의 전체 거리를 사용한다.
• 다익스트라 알고리즘은 목적 정점이 나타나면 종료하지만 프림 알고리즘은 모든 정점을 방문해야 종료한다.

그래프를 예시로 다익스트라 알고리즘의 동작에 대해 설명해 보겠습니다.

---

1

 

가중치가 부여된 그래프가 있습니다.

 

1를 시작 정점으로 잡고 퍼져나가는 것을 알아보겠습니다.

2까지 가는 중

 

---

구현

 

(1) : 순차 탐색을 이용한 방법으로 노드의 개수가 N이라고 할 때 각 노드마다 최소 거리값을 갖는 노드를 선택해야하는 순차 탐색이 수행되므로 (N - 1) X N = O(N ^ 2)의 시간이 걸린다.

#include <iostream>
#define INF 1000000000
#define N 8
using namespace std;

int weight[N][N] = { { 0, 2, INF, INF, 3, INF, INF, INF }, // 1
	  	     { 2, 0, INF, 1, 5, INF, INF, INF },   // 2
		     { INF, INF, 0, 2, INF, INF, 3, INF},  // 3
		     { INF, 1, 2, 0, 2, 4, INF, 5},        // 4
		     { 3, 5, INF, 2, 0, INF, INF, 3},      // 5
		     { INF, INF, INF, 4, INF, 0, 4, 1},    // 6
		     { INF, INF, 3, INF, INF, 4, 0, INF},  // 7
		     { INF, INF, INF, 5, 3, 1, INF, 0} };  // 8

bool visit[N];
int dist[N];
int min_node;

int get_small_node() {
	int min = INF;
	int minpos = 0;
	for (int i = 0; i < N; i++) {
		if (dist[i] < min && !visit[i]) {
			min = dist[i];
			minpos = i;
		}
	}
	return minpos;
}

void dijkstra(int start) {
	for (int i = 0; i < N; i++) {
		dist[i] = weight[start][i];
	}

	visit[start] = true;
	for (int repeat = 0; repeat < N - 1; repeat++) {
		min_node = get_small_node();
		visit[min_node] = true;
		for (int i = 0; i < N; i++) {
			if (!visit[i])
				if (dist[min_node] + weight[min_node][i] < dist[i])
					dist[i] = dist[min_node] + weight[min_node][i];
		}
	}
}

int main() {
	dijkstra(0);

	for (int i = 0; i < N; i++) {
		cout << dist[i] << " ";
	}

	return 0;
}

 

 

(2) : 우선순위 큐를 이용한 방법으로 간선의 수를 E(Edge), 노드의 수를 V(Vectex)라고 했을 때, O(E log V)가 된다.

#include <iostream>
#include <vector>
#include <queue>

#define number 9
#define INF 10000000

using namespace std;

vector<pair<int, int>> a[9];
int d[9];

void dijkstra(int start) {
	d[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(start, 0));
	
	while (!pq.empty()) {
		int current = pq.top().first;
		int distance =- pq.top().second;
		pq.pop();

		if (d[current] < distance) continue;
		
		for (int i = 0; i < a[current].size(); i++) {
			int next = a[current][i].first;
			int nextDistance = distance + a[current][i].second;
			if (nextDistance < d[next]) {
				d[next] = nextDistance;
				pq.push(make_pair(next, -nextDistance));
			}
		}
	}
}

int main() {
	for (int i = 1; i < number; i++) {
		d[i] = INF;
	}

	a[1].push_back(make_pair(2, 2));
	a[1].push_back(make_pair(5, 3));
	
	a[2].push_back(make_pair(1, 2));
	a[2].push_back(make_pair(4, 1));
	a[2].push_back(make_pair(5, 5));

	a[3].push_back(make_pair(4, 2));
	a[3].push_back(make_pair(7, 3));

	a[4].push_back(make_pair(2, 1));
	a[4].push_back(make_pair(3, 2));
	a[4].push_back(make_pair(5, 2));
	a[4].push_back(make_pair(6, 4));
	a[4].push_back(make_pair(8, 5));
	
	a[5].push_back(make_pair(1, 3));
	a[5].push_back(make_pair(4, 2));
	a[5].push_back(make_pair(8, 3));

	a[6].push_back(make_pair(4, 4));
	a[6].push_back(make_pair(7, 4));
	a[6].push_back(make_pair(8, 1));

	a[7].push_back(make_pair(3, 3));
	a[7].push_back(make_pair(6, 4));

	a[8].push_back(make_pair(4, 5));
	a[8].push_back(make_pair(5, 3));
	a[8].push_back(make_pair(6, 1));

	dijkstra(1);

	for (int i = 1; i < number; i++) {
		cout << d[i] << " ";
	}
}

---

2024-03-25 Python으로 작성

 

엄청 간결해진다.

from collections import deque

INF = 1e8
graph = {
    1: [(2, 2), (5, 3)],
    2: [(1, 2), (4, 1), (5, 5)],
    3: [(4, 2), (7, 3)],
    4: [(2, 1), (3, 2), (5, 2), (6, 4), (8, 5)],
    5: [(1, 3), (4, 2), (8, 3)],
    6: [(4, 4), (7, 4), (8, 1)],
    7: [(3, 3), (6, 4)],
    8: [(4, 5), (5, 3), (6, 1)]
}
d = [INF] * 9

def dijkstra(start):
       d[start] = 0
       pq = deque()
       pq.append((start, 0))

       while pq:
              current, distance = pq.popleft()
              distance = -distance

              if (d[current] < distance):
                     continue

              for i in range(len(graph[current])):
                     next, weight = graph[current][i]
                     nextDistance = weight + distance
                     if (nextDistance < d[next]):
                            d[next] = nextDistance
                            pq.append((next, -nextDistance))

dijkstra(1)

for i in range(1, 9):
       print(d[i], end = ' ')