그래프 최단 경로 탐색 알고리즘 - 다익스트라

Intro

 

이 알고리즘은 그래프에서 node A에서 B까지의 최단 경로를 구한다. 이 때 최단 경로란 시작 점부터 끝 점까지 이동하는 동안 거치는 가중치의 합이 최소가 되도록 하는 경로를 말한다. 가중치가 있는 그래프에서 5-10 으로 도착하는 것보다 1-2-3으로 도착하는 것이 더 최단 경로라고 할 수 있다. 만약 가중치가 없는 그래프에서는 BFS를 이용해 두 노드 사이의 최단 거리를 구하면 그것이 곧 최단 경로 탐색이 된다.

그래프,BFS 알고리즘 : maru20564.tistory.com/6

대표적인 그래프 탐색 알고리즘 DFS/BFS 이론

 

만약 가중치가 있는 그래프에서 최단 경로 탐색을 할 때 쓰는 알고리즘 중 하나로 가장 알려진 것은 다익스트라 알고리즘이다.

 

 

 

Dijkstra

 

다익스트라 알고리즘은 시작 노드에서 가장 최단 거리가 짧은 노드를 차례때로 선택하여 거리를 계산해나가는 알고리즘이다.

 

• 시작 노드 A를 기준으로 나머지 노드는 모두 미방문으로 초기화한다. 그리고 현재 연결되지 않은 값은 거리가 무한대이다.
• 시작 노드는 방문하며 거리가 0으로 시작한다.
• 아직 방문하지 않은 노드 중 A노드까지 가는 weight가 가장 짧은 노드를 탐색한다.
• A 노드에서 해당 노드까지 방문한 가중치의 합을 통해 해당 노드까지의 거리를 업데이트한다. 서로 비교하여 최소 weight만 남긴다.
• 모든 노드를 방문할 때까지 방문하면 최종 B노드까지의 최소 weight path를 구할 수 있다.

 

해당 알고리즘을 C++로 구현하면 다음과 같다.

 

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int dijkstra(vector<vector<pair<int, int>>> graph,int n, int start, int end) {
	if(start == end)
		return 0;

	//초기화
	int INF = 100000;
	int* dist = new int[n + 1];			//그래프 저장 때 0은 사용 안했기 때문에 +1
	bool* check = new bool[n + 1];
	bool end_check = false;

	for (int i = 1; i < n + 1; i++) {
		dist[i] = INF;
		check[i] = false;
	}

	//첫 노드와 그에 연결된 노드 업데이트
	dist[start] = 0;
	check[start] = true;

	for (int i = 0; i < graph[start].size(); i++)
		dist[graph[start][i].first] = graph[start][i].second;	//첫 노드와 연결된 가중치 == distance

	while (!end_check) {
		//min distance를 찾아 방문한다.
		int min_distance = INF;
		int min_node = -1;

		for (int i = 1; i < n + 1; i++) {
			if (check[i] == false && dist[i] != INF) {
				if (dist[i] < min_distance) {
					min_distance = dist[i];
					min_node = i;
				}
			}
		}

		//min distance 노드를 방문한 후 해당 노드와 연결되어있는 노드들의 start 노드까지의 가중치를 업데이트 한다.
		check[min_node] = true;
		for (int i = 0; i < graph[min_node].size(); i++) {
			//값이 더 작아질 때만 업데이트
			if(dist[graph[min_node][i].first] > dist[min_node] + graph[min_node][i].second)
				dist[graph[min_node][i].first] = dist[min_node] + graph[min_node][i].second;
		}

		//end check
		end_check = true;
		for (int i = 1; i < n + 1; i++) {
			if (check[i] == false)
				end_check = false;
		}
	}

	int res = dist[end];

	delete[] dist;
	delete[] check;

	return res;
}

int main(void)
{
	int n, m;
	cin >> n >> m; // node edge의 개수를 입력받음

	//graph 생성
	vector<vector<pair<int,int>>> graph;
	vector<pair<int,int>> edge;
	for (int i = 0; i < n + 1; i++)	//index 0은 사용 안함. node 번호 1부터 시작.
		graph.push_back(edge);

	//edge 입력
	for (int i = 0; i < m; i++) {
		int u, v, w;				//u 해당 노드, v 연결되는 노드, w 가중치
		cin >> u >> v >> w;

		//vertax 중복 예외처리
		for (int i = 0; i < graph[u].size(); i++) {
			if (graph[u][i].first == v) {
				graph[u].erase(graph[u].begin() + i);
				break;
			}
		}
        
        graph[u].push_back(make_pair(v, w));
        
        //양방향일 때
		for (int i = 0; i < graph[v].size(); i++) {
			if (graph[v][i].first == u) {
				graph[v].erase(graph[v].begin() + i);
				break;
			}
		}

		graph[v].push_back(make_pair(v, w));
	}

	int start, end, res;

	cout << "input start and end" << endl;
	cin >> start >> end;
    
	//예외처리
	if (start < 0 || start > n || end < 0 || end > n)
		return 1;

	res = dijkstra(graph, n, start, end);

	cout << res;

	return 0;
}

 

그래프 구현은 전에 그래프 때 만들었던 방식대로 vector를 사용한 인접 리스트 방식으로 거기에 weight를 추가하여 구현하였다. weight는 pair를 사용하여 붙여두었다.

 

• 실행 결과

간단 그래프 예시에 가중치를 붙여 최단 경로 가중치를 계산해 보았다. 그 결과는 다음과 같다.

 

1->3까지의 최단 거리

 

만약 DFS/BFS처럼 해당 노드까지의 최단 경로 path를 알고 싶으면 다익스트라 알고리즘에 추가하여 응용하면 된다.