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

대표적인 최단 경로 탐색 알고리즘입니다.
특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 그래프의 모든 간선이 0이상의 cost를 가져야 다익스트라 알고리즘을 사용할 수 있습니다.

로직

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 계산해 '최단 거리 테이블'을 업데이트 한다.
5. 3~4의 과정을 반복한다.

• 최단 거리 테이블 : 1차원 배열로 선언하며 start에서 N개 노드까지 가는데 필요한 최단 거리를 기록한다. N개 크기의 배열을 선언하고 큰 값INF을 넣어 초기화시킨다.
• 노드 방문 여부 체크 배열 : 방문한 노드인지 아닌지 기록하기 위한 배열

구현

1. Sequential Search

#include<iostream>
using namespace std;

#define MAX_N 6
#define INF (987654321)

int graph[MAX_N][MAX_N] = {
    {0,2,5,1,INF,INF},
    {2,0,3,2,INF,INF},
    {5,3,0,3,1,5},
    {1,2,3,0,1,INF},
    {INF,INF,1,1,0,2},
    {INF,INF,5,INF,2,0}
};

int getMinIdx(int nodes[MAX_N], int visited[MAX_N]) { // 방문하지 않은 노드중 최소 비용을 가지고 있는 노드의 인덱스 반환
    int min = INF;
    int index = 0;
    for (int i = 0; i < MAX_N; i++) {
        if (!visited[i] && nodes[i] < min) {
            index = i;
        }
    }
    return index;
}

void dijkstra2(int arr[MAX_N][MAX_N], int start, int dist[MAX_N]) {
    int visited[MAX_N] = { 0, };
    for (int i = 0; i < MAX_N; i++) {
        dist[i] = arr[start][i]; // dist배열에 인접노드 초기화하기
    }
    visited[start] = 1;
    for (int i = 0; i < MAX_N-1; i++) { // 시작점 빼고 하나씩 방문
        int n_new = getMinIdx(dist, visited); // 가까운 점 찾기
        visited[n_new] = 1; // 가까운 점 방문처리
        for (int j = 0; j < MAX_N; j++) { // 가까운 점 기준으로 둘러보기
            if (!visited[j]) { // dist값 갱신
                if (dist[j] > dist[n_new] + arr[n_new][j]) {
                    dist[j] = dist[n_new] + arr[n_new][j];
                }
            }
        }
    }
}

int main(int argc, char** argv)
{
    int dist[MAX_N];
    int start = 0;
    dijkstra2(graph, start, dist);
    for (int i = 0; i < MAX_N; i++) {
        printf("%d->%d : %d\n", start, i, dist[i]);
    }
	return 0;
}

위의 알고리즘은 선형 탐색으로 O(N^2)의 시간 복잡도가 형성되며 정점의 개수는 많은데 간선은 적을 때 비효율적으로 작용할 수 있습니다. 그래서 힙을 사용하여 시간 복잡도 O(N*logN)으로 구현해보았습니다.

2. Priority Queue Search

• 인접행렬이용

#include <queue> // 우선순위 큐를 위한 라이브러리
#include <iostream> // cout사용을 위한 라이브러리
using namespace std;

#define MAX_N 6
#define INF (987654321)


int graph[MAX_N][MAX_N] = {
    {0,2,5,1,INF,INF},
    {2,0,3,2,INF,INF},
    {5,3,0,3,1,5},
    {1,2,3,0,1,INF},
    {INF,INF,1,1,0,2},
    {INF,INF,5,INF,2,0}
};

void dijkstra(int arr[MAX_N][MAX_N], int start, int dist[MAX_N]) {
    priority_queue< pair< int, int >> pq;
    for (int i = 0; i < MAX_N; i++) {
        dist[i] = INF;
    }
    pq.push({ 0,start }); // dist, destination
    while (!pq.empty()) {
        int cur_dist = -pq.top().first;
        int cur_node = pq.top().second;
        pq.pop();

        for (int i = 0; i < MAX_N; i++) {
            int next_dist = cur_dist + arr[cur_node][i];
            if (dist[i] > next_dist) {
                dist[i] = next_dist;
                pq.push({ -next_dist, i });
            }
        }
    }
}


int main()

{
    int dist[MAX_N];
    int start = 0;
    dijkstra(graph, start, dist);
    for (int i = 0; i < MAX_N; i++) {
        printf("%d->%d : %d\n", start, i, dist[i]);
    }

    printf("\n");

    return 0;

}

---

• 인접리스트이용

int dijkstra(int start) {
	memset(dist,1000000,sizeof(dist));
	dist[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ -0,start });
	while (!pq.empty()) {
		int cur_dist = -pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		for (int i = 0; i < v[cur_node].size(); i++) {
			int next_dist = cur_dist + v[cur_node][i].second;
			int next_node = v[cur_node][i].first;
			if (dist[next_node] > next_dist) {
				dist[next_node] = next_dist;
				pq.push({ -next_dist, next_node });
			}
		}
	}


	return dist[X];
}