Computer Science & Engineering

최단 경로를 탐색하는 알고리즘에서 한 정점에서 다른 모든 정점까지 탐색하는 알고리즘에는 대표적으로 두 가지가 있다. 하나는 다익스트라 알고리즘이고 다른 하나는 벨만-포드 알고리즘이다. 두 알고리즘의 차이점은 대부분 알다시피 간선의 가중치에 음수가 있느냐(벨만-포드) 없느냐(다익스트라)이다.

이 점은 누구나 알고 있지만 실제로 코드에서 어떠한 차이점이 있는 지는 설명만 보고 알기 어려워 비교를 해보려고 한다.

우선 대표적인 다익스트라 알고리즘 문제인 백준 1753번 문제를 푼 알고리즘이다.

www.acmicpc.net/problem/1753 

다익스트라 알고리즘

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

int INF = 2123456789;

struct edge { //간선의 가중치와 목적지 구조체
	int w, v;
};

vector<edge> g[20001]; //그래프 간선 구조체
int dist[20001]; //시작점에서 모든 정점까지의 최단 경로를 저장할 dp배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
	int V, E, K; cin >> V >> E >> K;
	for(int i = 0; i < E; i++) {
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({w, v}); //그래프의 간선 정보 입력
	}

	fill(dist + 1, dist + 1 + V, INF); //시작점에서 모든 정점은 아직 방문하지 않았으므로 INF로 초기화

	using P = pair<int,int>; //pair 표현 간소화
	priority_queue<P, vector<P>, greater<P>> pq; //최소힙 구현
	pq.push({0, K}); //처음 시작점 push
	dist[K] = 0; //시작점은 최단 경로 0으로 초기화
	while(!pq.empty()) { //더 이상 갱신할 최단 경로가 없을 때까지
		P tmp = pq.top(); pq.pop(); //새로 뻗을 수 있는 간선 중에 가중치가 가장 작은 값
		int cur_w = tmp.first;
		int cur = tmp.second;

		if(dist[cur] < cur_w) continue; //최소값 아닐 경우 건너뛰기

		for(edge next : g[cur]) { //새로 뻗은 간선에서 뻗을 수 있는 모든 간선에 대하여
			if(dist[next.v] > dist[cur] + next.w) { //최소값을 갱신할 수 있으면 갱신하고 우선순위 큐에 push
				dist[next.v] = dist[cur] + next.w;
				pq.push({dist[next.v], next.v});
			}
		}
	}
	for(int i = 1; i <= V; i++) {
		if(dist[i] == INF) //최단 경로가 없으면 INF
			cout << "INF" << '\n';
		else
			cout << dist[i] << '\n'; //최단 경로가 있으면 최단 경로 출력
	}
	return 0;
}

www.acmicpc.net/problem/11657

벨만 포드 알고리즘

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

struct edge { //간선의 정보를 저장할 구조체
    long long w, v;
};

int INF = 987654321;
vector<edge> g[501]; //그래프 간선 표현 vector배열
long long dist[501]; //최소값을 저장할 dp배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N >> M;
    for(int i = 0; i < M; i++) {
        long long a, b, c; cin >> a >> b >> c;
        g[a].push_back({c, b}); //간선 정보 저장
    }
    fill(dist, dist+N+1, INF); //모든 정점까지 최단 경로 INF로 초기화
    dist[1] = 0; //시작점 최단 경로 0으로 초기화

    for(int i = 1; i <= N; i++) { //N번 반복
        for(int j = 1; j <= N; j++) { //j에서 다른 정점으로 뻗을 수 있는 간선의 정점 최솟값 갱신
            if(dist[j] == INF) continue; //최단 경로가 없는 경우 건너뛰기
            for(edge next : g[j]) { //j에서 뻗을 수 있는 간선에 대하여
                if(i < N) { //모든 정점 갱신할 수 있는 N-1번 반복까지는 최단 경로 갱신
                    if(dist[next.v] > dist[j] + next.w) { //최단 경로 갱신
                        dist[next.v] = dist[j] + next.w;
                    }
                }
                else { //만약 모든 최단 경로를 갱신한 다음 N번째에도 최솟값을 갱신하는 경우
                    if(dist[next.v] > dist[j] + next.w) { //무한히 최단 경로를 갱신하므로 -1출력하고 프로그램 종료
                        cout << -1 << '\n';
                        return 0;
                    }
                }
                
            }
        }
    }
    for(int i = 2; i <= N; i++) {
        if(dist[i] == INF) cout << -1 <<'\n'; //최단 경로가 없는 경우 -1 출력
        else cout << dist[i] <<'\n'; //최단 경로 출력
    }

}

위와 같이 두 가지 알고리즘을 작성해보았다.

간선에 음의 가중치가 없는 다익스트라의 경우 최솟값이 무한히 갱신되는 경우가 없기 때문에

우선순위 큐를 이용하여 갱신할 최단 경로가 존재하지 않을 때까지만 반복하면 된다.

하지만 음의 가중치가 있는 벨만 포드의 경우 다익스트라처럼 우선순위 큐를 사용할 경우

최단 경로를 갱신하는 경우 우선선위 큐에 push하고 큐가 모두 빌 때까지 반복하므로 아래 그림과 같이 1에서 4까지의 경로가 2-3-4를 순환하면서 최단경로가  -1씩 무한히 갱신될 수 있다.

따라서 정점의 수 N에 대하여 간선의 수는 최대 N(N-1)이므로 모든 정점에 대하여 N-1번 반복하면 모두 갱신할 수 있게 된다. 따라서 N번째 반복에서 최단 경로가 또 한 번 갱신된다면 이는 위의 그림처럼 무한히 갱신되는 경우가 된다.

이러한 이유가 벨만 포드에서 우선순위 큐가 빌 때까지가 반복문의 조건이 아닌 이유이다.