[C++][다익스트라 알고리즘] 구현 방법

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

다이나믹 프로그래밍(DP)를 활용한 최단 경로(Shortest Path) 탐색 알고리즘.

하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.

 

구현은 Greedy 알고리즘이나 DP 알고리즘을  사용하는데,

 

Greedy 알고리즘을 사용할 수 있는 이유는 인접한 노드들 중 가장 작은 비용을 갖고 있는 노드를 선택하여 탐색을 진행하기 때문이다.

 

DP 알고리즘을 활용할 수 있는 이유는 "최단 거리는 여러 개의 최단 거리들"로 이루어져있기 때문이다.

(최단 거리 = 최단 거리 정보들의 합)

출처: Wikipedia Dikstra Algorithm 

위의 그림은 a(1)와 b(5)사이의 최단 경로를 찾는 다익스트라 알고리즘의 흐름을 보여준다.

 

가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. (참고: 인접한 노드에 모두 방문하면 빨간색으로 표시되며 out 이라고 뜬다.)

 

 

▶ 구현 방법과 원리

1) 비용을 담을 배열을 만들고, 무한대(INF)의 값으로 초기화 한다.

    방문체크 배열을 만들고, false로 초기화 한다.

for (int i = 0; i < V; i++)
	dist[i] = INT_MAX, visited[i] = false;

 

2) 시작노드를 방문노드로 체크한다. 시작노드와 인접한 노드들의 거리를 비교해서 비용을 업데이트 한다.

visited[current_node] = true;

for (int v = 0; v < V; v++)
	if (!visited[v] && graph[current_node][v] && dist[current_node] != INT_MAX 
    	&& dist[current_node] + graph[current_node][v] < dist[v]){
			dist[v] = dist[current_node] + graph[current_node][v];
    }

3) 시작노드와 연결된 노드들 중 비용이 가장 적은 노드를 선택하여 이동한다.

int u = minDistance(dist, visited);

4) 이동한 노드를 방문노드로 체크한다. 노드와 연결된 노드들의 거리를 비교해서 비용을 업데이트 한다.

visited[u] = true;

for (int v = 0; v < V; v++)
	if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]){
			dist[v] = dist[u] + graph[u][v];
    }

4) 도착지점에 다다를 때까지 반복한다.

 

 

▶ 전체코드

// A C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <limits.h>
#include <stdio.h>

#define V 9

int minDistance(int dist[], bool visited[]){
	int min = INT_MAX, min_index;

	for (int v = 0; v < V; v++)
		if (visited[v] == false && dist[v] <= min)
			min = dist[v], min_index = v;

	return min_index;
}

int printSolution(int dist[], int n){
	printf("Vertex   Distance from Source\n");
	for (int i = 0; i < V; i++)
		printf("%d \t\t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src){
	int dist[V]; 
	bool visited[V];

	for (int i = 0; i < V; i++)
		dist[i] = INT_MAX, visited[i] = false;

	dist[src] = 0;

	for (int count = 0; count < V - 1; count++) {
		int u = minDistance(dist, visited);
		visited[u] = true;
		for (int v = 0; v < V; v++)
			if (!visited[v] && graph[u][v] && dist[u] != INT_MAX
				&& dist[u] + graph[u][v] < dist[v])
				dist[v] = dist[u] + graph[u][v];
	}
	printSolution(dist, V);
}

int main(){
	int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
						{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
						{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
						{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
						{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
						{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
						{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
						{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
						{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

	dijkstra(graph, 0);

	return 0;
}

▶ 출력화면

Vertex   Distance from Source
0          0
1          4
2          12
3          19
4          21
5          11
6          9
7          8
8          14

출처: https://www.geeksforgeeks.org/c-program-for-dijkstras-shortest-path-algorithm-greedy-algo-7/

 

 

▶ 관련문제

1261번: 알고스팟