[C++] 다익스트라 & 벨만-포드 알고리즘 구현하기

🔵 다익스트라 알고리즘

출발 노드에서 그래프 내의 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다.

간선의 가중치가 음수가 아니어야 하며, 일반적으로 단일 출발점 최단 경로 문제를 해결할 때 사용된다.

 

다익스트라 알고리즘은 기본적으로 그리디 방식으로 작동한다.

1. 시작 노드로부터 거리를 모두 무한대로 초기화한다. (단 시작 노드 자신까지의 거리는 0으로 설정한다.)
2. 아직 방문하지 않은 노드들 중에서, 시작 노드로부터의 거리가 가장 짧은 노드를 선택한다.
3. 선택된 노드를 방문 처리하고, 이제 그 노드까지의 최단 거리는 확정된 것으로 간주한다.
4. 선택된 노드를 경유하여 인접한 다른 노드들로 갈 때의 거리를 계산하고, 현재까지 알려진 그 노드까지의 최단거리와 비교하여 더 짧으면 갱신한다.
5. 이 과정을 모든 노드를 방문할 때까지 반복한다.

 

🔷 구현 방식 - 인접 행렬

노드의 수가 적고 (1000 이하) 간선이 많은 밀집 그래프에 적합하고, 간편하게 구현할 수 있다.

특정 간선의 존재 여부를 매우 빠르게 확인할 수 있기 때문에(O(1)), 두 노드 간 연결 여부를 자주 확인해야 하는 문제에는 이 방식이 적합하다.

노드의 개수를 N, 간선의 개수를 E라고 할 때, 시간 복잡도는 O(N^2)이다.

 

그래프는 배열로 표현한다.

x와 y 사이 가중치가 3이라는 간선이 있다고 가정했을 때, graph[x][y] = 3 으로 표현한다.

#include <string>
#include <vector>
#include <tuple>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();
const int MAX_NODES = 100;
int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];

vector<int> solution(int start, int numNodes, vector<tuple<int, int, int>> edges)
{
	// 그래프 및 방문 여부 초기화
	for (int i = 0; i < MAX_NODES; i++)
	{
		fill_n(graph[i], MAX_NODES, INF);
		visited[i] = false;
	}

	// 입력받은 간선 정보를 그래프로 표현
	for (const auto& [from, to, weight] : edges)
	{
		graph[from][to] = weight;
	}

	// 시작 노드를 제외한 모든 노드의 최소 비용을 INF로 초기화
	vector<int> distances(numNodes, INF);

	// 시작 노드로부터 특정 노드까지의 확정된 최단 거리
	distances[start] = 0;

	for (int i = 0; i < numNodes - 1; i++)
	{
		int minDistance = INF;
		int closestNode = -1;

		// 최소 거리 노드 찾기
		// 우선 순위 큐처럼 동작
		for (int j = 0; j < numNodes; j++)
		{
			if (!visited[j] && distances[j] < minDistance)
			{
				minDistance = distances[j];
				closestNode = j;
			}
		}

		// 예외 발생 시 정지
		if (closestNode == -1) break;

		// 찾은 노드를 방문 처리
		visited[closestNode] = true;

		// 인접 노드에 대한 거리 업데이트
		for (int j = 0; j < numNodes; j++)
		{
			int newDistance = distances[closestNode] + graph[closestNode][j];
			if (!visited[j] && graph[closestNode][j] != INF && newDistance < distances[j])
				distances[j] = newDistance;
		}
	}

	return distances;
}

위 코드에서 우선 순위 큐처럼 동작하는 부분을 실제 우선 순위 큐로 구현하지 않은 이유가 있다.

우선 순위 큐로 했을 때 얻을 수 있는 이점은 시간 복잡도에서의 이점인데, 코드 마지막 for문의 영향으로 어차피 시간 복잡도에 큰 이점이 없어지기 때문에 비교적 간단한 구현으로 처리하였다.  

 

🔷 구현 방식 - 인접 리스트 & 우선순위 큐 

노드의 수가 많고, 간선의 수가 적은 희소 그래프에 특히 적합하다. 구현이 인접 행렬보다 약간 복잡할 수 있지만, 특별한 경우가 아니라면 전체 시간 복잡도가 O(V+E), 또는 O(ElogV) 등으로 훨씬 효율적이다.

 

vector<vector<pair<int, int>>> 형식으로 그래프를 표현한다.
x와 y 사이 가중치가 3이라는 간선이 있다고 가정했을 때, graph[x]에는 pair<int, int> 형식으로 {y, 3}이 들어있다.

#include <string>
#include <vector>
#include <tuple>
#include <limits>
#include <queue>

using namespace std;

const int INF = numeric_limits<int>::max();

struct Compare
{
	bool operator()(const pair<int, int>& a, const pair<int, int>& b)
	{
		return a.first > b.first; // 거리가 작은 순대로 정렬
	}
};

vector<int> solution(int start, int numNodes, vector<tuple<int, int, int>> edges)
{
	// 간선 정보를 활용해서 인접 리스트를 생성
	vector<vector<pair<int, int>>> adjList(numNodes);
	for (const auto& [from, to, weight] : edges)
		// emplace_back: 객체 생성에 필요한 인자만 받은 후 함수 내에서 객체를 생성해 삽입한다.
		adjList[from].emplace_back(to, weight);

	// 시작 노드를 제외한 모든 노드의 최소 비용을 INF로 초기화
	vector<int> distances(numNodes, INF);
	distances[start] = 0;

	// 우선순위 큐에 시작 노드 추가
	priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
	pq.push({ 0, start });

	// 노드의 방문 여부를 저장하는 배열
	vector<bool> visited(numNodes, false);

	while (!pq.empty())
	{
		int currentDistance = pq.top().first;
		int currentNode = pq.top().second;
		pq.pop();

		// 이미 방문한 노드인 경우 무시
		if (visited[currentNode]) continue;

		// 현재 노드를 방문 처리
		visited[currentNode] = true;

		// 인접 노드에 대한 거리 업데이트
		for (const auto& [neighbor, weight] : adjList[currentNode])
		{
			int newDistance = distances[currentNode] + weight;
			if (newDistance < distances[neighbor])
			{
				distances[neighbor] = newDistance;
				pq.push({ newDistance, neighbor });
			}
		}
	}
	return distances;
}

 

🔹 Compare를 왜 함수 포인터 대신 구조체로 선언하였는가?

struct Compare
{
	bool operator()(const pair<int, int>& a, const pair<int, int>& b)
	{
		return a.first > b.first; // 거리가 작은 순대로 정렬
	}
};

C++에서 비교자를 정의하는 방법은 크게 함수 포인터, 함수 객체, 람다 표현식이 있다.

priority_queue의 비교자는 함수 객체 혹은 람다 타입이어야 한다.

따라서 비교자를 struct로 구현했다. 

 

🔹 emplace_back은 무엇인가?

	for (const auto& [from, to, weight] : edges)
		adjList[from].emplace_back(to, weight);

push_back과 유사하게 컨테이너 끝에 요소를 추가하는 역할을 한다.

 

push_back은 완전히 구성된 객체를 받아서 컨테이너에 추가한다.

emplace_back은 객체로 생성하는 데 필요한 인자들을 직접 받는다. 그리고 컨테이너 내부에서 해당 인자들을 사용하여 객체를 그 자리에서 바로 생성한다.

 

🔹 우선순위 큐 선언

// priority_queue<  ElementType,  ContainerType,  ComparatorType  >  variableName;

priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;

ElementType

우선순위 큐에 저장될 요소의 타입

 

ContainerType

우선순위 큐가 내부적으로 요소를 저장하고 관리하는 데 사용할 기반 컨테이너의 타입.

기본값은 std::vector이므로 이 코드에서는 이 부분을 명시적으로 지정하지 않아도 된다.

 

ComparatorType

우선순위 큐 내부에서 두 요소를 비교하여 어떤 것이 더 높은 우선순위를 가지는지 결정하는 비교자 타입(함수 객체 혹은 람다).

 

🔵 벨만-포드 알고리즘

다익스트라 알고리즘과 비슷하게 단일 출발점 최단 경로를 찾는 알고리즘이다.

가장 중요한 특징은 다음과 같다.

• 음수 가중치 간선이 있는 그래프에서 최단 경로를 찾을 수 있다.
• 음수 가중치 사이클을 감지할 수 있다.

음수 가중치 사이클이란 경로를 따라가면 총 비용이 계속 감소하는 사이클이다.

이 사이클이 존재하면 최단 경로가 무한히 작아질 수 있으므로, 최단 경로가 정의되지 않는다.

 

벨만-포드 알고리즘은 DP 원리를 사용하여 최단 경로를 찾는다.

다익스트라가 가장 가까운 노드를 찾아 확정하는 탐욕적인 방식이라면, 벨만-포드는 모든 간선을 여러 번 이완하여 점진적으로 최단 경로를 찾아가는 방식이다.

(Relaxation(이완)이란, 현재까지 알려진 어떤 노드까지의 최단 거리가 있을 때, 더 짧은 경로를 발견해 이를 갱신하는 과정을 말한다.)

1. 시작점을 설정한다.
2. 모든 간선을 (V - 1)번 반복해서 이완한다. (최단 경로는 사이클이 없는 한 최대 V - 1개의 간선으로 이루어진다.)
3. 마지막으로 한 번 더 모든 간선을 이완해 보고, 이때도 갱신이 발생하면 음수 사이클이 있음을 확정한다.
4. 결과를 반환한다.

#include <string>
#include <vector>
#include <tuple>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();


vector<int> solution(int num_vertices, vector<tuple<int, int, int>> edges, int source)
{
	vector<vector<pair<int, int>>> graph(num_vertices);

	// 간선 정보를 활용해서 인접 리스트 생성
	for (auto& [from, to, weight] : edges)
		graph[from].emplace_back(to, weight);
	
	// 현재까지 구한 최소 비용을 INF로 설정
	// 시작 노드 설정
	vector<int> distances(num_vertices, INF);
	distances[source] = 0;

	// 정점의 개수 - 1 만큼 최소 비용 갱신
	for (int i = 0; i < num_vertices - 1; i++)
	{
		for (int u = 0; u < num_vertices; u++)
		{
			for (const auto& [v, weight] : graph[u])
			{
				if (distances[u] + weight < distances[v])
					distances[v] = distances[u] + weight;
			}
		}
	}

	// 음의 순환이 있는지 확인
	for (int u = 0; u < num_vertices; u++)
	{
		for (const auto& [v, weight] : graph[u])
		{
			if (distances[u] + weight < distances[v])
				// 음의 순환 발견
				return vector<int>(1, -1);
		}
	}

	return distances;
}

노드의 개수를 N, 간선의 개수를 E라 할 때, 노드의 개수만큼 최단 경로를 갱신하는 연산을 하므로 시간 복잡도는 O(N*E)이다.

 

벨만-포드 알고리즘은 다익스트라 알고리즘과는 달리 음수 가중치가 있다고 가정하므로 한 번의 선택으로 최단 거리가 확정될 수 없다고 본다.

이전 반복에서 발생한 distances 값 변화를 기반으로, 아직 발견되지 않은 더 짧은 경로를 찾아내기 위해 모든 간선을 다시 한번 재검토하고 정보가 충분히 전파되게 한다.

따라서 모든 간선을 여러 번(V - 1)번 반복하여 모든 경로가 충분히 이완될 기회를 준다.