최단 경로 구하기 (다익스트라, 벨만-포드)

1. 다익스트라 알고리즘

---

가중치가 있는 그래프의 최단경로를 구할 때 사용하는 알고리즘

 

다익스트라 알고리즘의 동작 방식은

• 모든 노드의 최소 비용을 INF로 초기화한다.
• 시작한 노드의 최소비용은 0, 직전 노드는 자기 자신으로 두고 시작
• 이후 최소 비용이 가장 낮으면서 방문하지 않은 노드를 선택하여 최소 비용을 업데이트 한다.

아래의 그림을 통해 어떤 방식으로 동작하는지 알 수 있다.

• 최소 비용이 가장 낮은 A로 시작하여 모든 연결된 노드의 최소비용을 갱신 (A 방문)
• 이후 최소비용이 가장 낮은 E노드를 시작으로 더 작은 최소비용이 되는 경로가 있다면 갱신 A->E->C가 기존의 A->C 보다 최소비용이 작으므로 갱신! (E 방문)
• 이 방식을 모든 노드 방문할 때 까지 반복하기

결과

• 우리가 C까지의 경로를 알고 싶다면, 
  • C의 직전 노드는 E, E의 직전 노드는 A 이므로 A -> E -> C임을 알 수 있다.
  • 최소 비용은 3 (C의 최소비용) 임을 알 수 있다.
• 주의점으로는 만약 음의 가중치가 있는 그래프의 경우 다익스트라 알고리즘은 제대로 동작하지 않게 된다.
  
  • 다익스트라 알고리즘은 크게 그리디 식으로 동작하는데, (가장 짧은 거리)
  • 음의 가중치가 있는 그래프의 경우, 최소 경로의 갱신이 제대로 이루어지지 않는 경우가 있다.
  • 그러나 양의 가중치만 있는 경우, 벨만-포드보다 효율적인 알고리즘이다.

음의 가중치를 가진 그래프 예시)

• D까지의 경로의 최소 비용은 A->C->B->D 이므로 -1인데
• 아래 표를 통해서 얻은 값은 2가 된다.
• 그 이유는 C를 방문하는 순간 B까지의 최소 비용은 업데이트가 되지만
• C에서 D로 가는 경로가 없어서 D까지의 최소비용이 업데이트 되지 않기 때문이다.
• 이런 문제를 해결하기 위해서는 벨만-포드 알고리즘을 사용한다.

 

 

2. 벨만-포드 알고리즘

---

벨만-포드와 다익스트라의 가장 큰 차이점은 벨만-포드의 경우 매 단계마다 간선의 가중치를 다시 구해서 최소 비용을 갱신한다는 점이다.

그 결과로 음의 가중치를 가진 그래프에서도 제대로 동작한다.

 

벨만 포드 알고리즘의 동작 방식은

• 다익스트라와 같은 방식으로 초기화 해주고
• 시작점부터 시작해서 모든 정점과의 최소비용 비교를 통해서 더 작은 최소비용이 발견되는 경우 업데이트를 해주게 된다.
• 아래와 같은 사이클을 정점개수-1 만큼 반복해주어야 한다.
  
  • 그 이유는 위에서 언급했던 다익스트라의 문제점인 음의 가중치가 있는 경로를 업데이트 하지 않는 문제를 해결하기 위해서 이다.
  • 한번 사이클을 돈 후에 가중치가 업데이트 되면, 해당 가중치를 가지고 한번 더 같은 경로를 순환하면 음수의 가중치 또한 업데이트가 가능해진다.
  • 결과적으로 1번의 순환동안 1개의 최단 경로가 확정되게 된다.

참고) 전체 동작 방식 영상: https://www.youtube.com/watch?v=obWXjtg0L64

주의) 음의 순환

• 음의 순환이 존재하면, 무한으로 순환하면서 최소비용이 계속 줄어드는 문제가 생긴다.
• 그렇기 때문에 모든 간선을 체크 후 한번 더 순환을 통해서 음의 순환이 있는지를 체크하는 부분이 있어야 한다.

 

3. 코드

---

배열을 사용한 다익스트라

#include <iostream>
#include <vector>
#include <tuple>
#include <climits>
using namespace std;

int board[10000][10000];
int vis[10000];

vector<int> solution(int start, int numNodes, vector<tuple<int, int, int>>edges)
{
	//board, vis 배열 초기화
	for (int i = 0; i < numNodes; ++i)
	{
		vis[i] = 0;
		for (int j = 0; j < numNodes; ++j)
		{
			board[i][j] = INT_MAX;
		}
	}

	//board 배열에 가중치 대입
	for (int i = 0; i < edges.size(); ++i)
	{
		board[get<0>(edges[i])][get<1>(edges[i])] = get<2>(edges[i]);
	}

	//거리 배열 초기화
	vector<int> distance(numNodes, INT_MAX);
	distance[start] = 0;

	for (int i = 0; i < numNodes - 1; ++i)
	{
		int minDist = INT_MAX;
		int closeNode = -1;

		//최소 비용이 가장 작은 노드 찾기
		for (int j = 0; j < numNodes; ++j)
		{
			if (!vis[j] && distance[j] < minDist)
			{
				minDist = distance[j];
				closeNode = j;
			}
		}

		vis[closeNode] = 1;

		//거리 업데이트
		for (int j = 0; j < numNodes; ++j)
		{
			int newDist = distance[closeNode] + board[closeNode][j];
			if (!vis[j] && board[closeNode][j] != INT_MAX && newDist < distance[j])
			{
				distance[j] = newDist;
			}
		}

	}

	return distance;
}

 

우선순위 큐를 사용한 다익스트라

https://www.acmicpc.net/problem/1753

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

int v, e, st;

vector<pair<int, int>> adj[20005];
const int INF = 1e9 + 10;
int dist[20005];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> v >> e >> st;
	fill(dist, dist + v + 1, INF);

	while (e--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ w, v });
	}

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

	//시작점 처리
	dist[st] = 0;

	//pq에 시작점 넣기
	pq.push({ dist[st], st });
	while (!pq.empty())
	{
		//w가 가장 작은 값을 cur로 설정함
		auto cur = pq.top();
		pq.pop();

		if (dist[cur.second] != cur.first)
			continue;
		for (auto nxt : adj[cur.second])
		{
			//dist에 적혀있는 값보다 새롭게 갱신할 값이 더 크면 continue;
			if (dist[nxt.second] <= dist[cur.second] + nxt.first)
				continue;
			//갱신할 값이 작은 경우 dist 업데이트
			//1 - > 2 인 경우
			//INF > 0 + 3 이므로 dist[2] = 3으로 업데이트
			dist[nxt.second] = dist[cur.second] + nxt.first;
			//업데이트 된 경우는 pq에 값 추가
			pq.push({ dist[nxt.second], nxt.second });
		}
	}
	for (int i = 1; i <= v; ++i)
	{
		if (dist[i] == INF)
			cout << "INF\n";
		else
			cout << dist[i] << "\n";
	}
}

 

벨만 포드 코드

#include <iostream>
#include <vector>
#include <tuple>
#include <climits>
using namespace std;

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

	//graph 값 넣기
	for (auto& edge : edges)
	{
		int from, to, weight;

		tie(from, to, weight) = edge;
		graph[from].emplace_back(to, weight);
	}

	//distance 초기화
	vector<int> distance(num_vertices, INT_MAX);
	distance[source] = 0;

	//N-1 번 반복
	for (int i = 0; i < num_vertices - 1; ++i)
	{
		//모든 정점을 보면서 distance값 업데이트
		for (int u = 0; u < num_vertices; ++u)
		{
			for (const auto& [v, weight] : graph[u])
			{
				//기존의 값보다 더 작을 때
				if (distance[u] + weight < distance[v])
				{
					distance[v] = distance[u] + weight;
				}
			}
		}
	}

	//음의 순환 체크
	for (int u = 0; u < num_vertices; ++u)
	{
		for (const auto& [v, weight] : graph[u])
		{
			if (distance[u] + weight < distance[v])
			{
				return vector<int>(1, -1);
			}
		}
	}
	return distance;
}