벨만 포드 알고리즘

다익스트라 알고리즘은 하나의 시작점에서 주어진 모든 정점까지의 최단 경로의 길이를 알려주는 알고리즘으로, 간선의 가중치가 전부 양수인 경우에 한하여 적용할 수 있었습니다.

 

2020/08/31 - [알고리즘] - 최단 경로 알고리즘 - [1] 다익스트라 알고리즘

 

벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 시작점이 정해져 있는 단일 시작점 알고리즘이지만, 음수 가중치에 있을 때에도 그래프 상의 모든 정점에 대한 최단 경로를 알아낼 수 있습니다.

 

이제 벨만-포드 알고리즘의 동작 과정을 예시로 알아보겠습니다

---

 

 

 

먼저, 시작점 1을 제외한 모든 정점의 최단 경로 길이를 Max 값으로 초기화 시켜줍니다. 시작점의 경로 길이는 0입니다.

 

 

정점 1에 붙어있는 모든 간선을 체크합니다.

 

1번 노드까지의 비용 + 1번에서 2번으로 가는 비용 = 5 가 Max보다 작으니 2번 노드까지의 비용은 5가 됩니다.

 

정점 2에 붙어있는 모든 간선을 체크합니다.

2번 노드까지의 비용 + 2번에서 4번으로 가는 비용 = 8 이 Max보다 작으니 4번 노드까지의 비용은 8이 됩니다.

2번 노드까지의 비용 + 2번에서 5번으로 가는 비용 = 4 가 Max보다 작으니 5번 노드까지의 비용은 4가 됩니다.

 

정점 3에 붙어있는 모든 간선을 체크합니다.

 

이 경우에는 두 가지로 나눠서 생각할 수 있습니다.

 

1) 3번 노드까지의 비용 + 3번에서 2번으로 가는 비용 =  Max+6이 Max보다 크니 갱신하지 않고 넘어갑니다.

2) 3번 노드까지의 비용이 초기값 Max와 동일하므로 탐색하지 않습니다.

 

이번 포스팅에서는 2번 방법으로 알고리즘을 설명하겠습니다. (문제에 따라 전자를 택해야 할 수도 있습니다.)

 

정점 4에 붙어있는 모든 간선을 체크합니다.

 

간선이 없으니 넘어갑니다.

 

 

정점 5에 붙어있는 모든 간선을 체크합니다.

5번 노드까지의 비용 + 5번에서 3번으로 가는 비용 = 12 가 Max보다 작으니 3번 노드까지의 비용은 12가 됩니다.

 

모든 정점을 한 번씩 돌면 모든 간선을 한 번씩 탐색할 수 있습니다.

이 때, 시작점으로부터 하나의 간선만큼 떨어진 정점까지의 최단경로는 확정될 수 있습니다.

 

V 개의 정점을 가진 그래프에서 최단경로가 거쳐야 할 간선의 개수는 최소 1개 최대 V-1 개 입니다.

즉, V-1 개의 간선만큼 떨어진 정점의 최단경로를 확정하기 위해선 모든 정점을 V-1 번 돌아야합니다.

 

마저 최단 경로를 완성시키기 위해 정점을 두 번째 돌아봅시다.

 

1번 정점부터 마지막 정점까지 돌아봤지만 최단 경로가 더 이상 갱신이 되지 않습니다.

이런 그래프의 경우 굳이 V-1 번 만큼 각 정점들을 돌아다닐 필요가 없으니 탐색을 종료합니다.

 

V-1 번 걸릴 것 같았던 탐색은 두 번 만에 탐색이 종료되었습니다.

 

이제 숫자를 약간 바꿔서 동일한 방법으로 탐색해보겠습니다.

 

 

위에서 말씀드린 방법으로 모든 정점을 1번부터 5번까지 한 바퀴 돌았을 때의 각 정점 별 최단 경로입니다.

음수 가중치가 존재함을 주목해야 합니다.

 

두 바퀴 돌았을 때의 최단 경로입니다.

 

세 바퀴 돌았을 때의 모습입니다.

 

 

네 바퀴 돌았을 때의 모습입니다.

계획대로라면 모든 정점을 V-1 번 돌아야 (정점이 다섯개니까 지금) 최단 경로가 완성이 되어있어야 합니다.

 

V 번 돌아도 최단 경로가 계속해서 갱신이 되며, 앞으로도 갱신이 멈추지 않을 것 같습니다.

 

2, 3, 5 번 사이클을 돌 때 가중치의 합이 0미만이므로, 경로를 최대한 짧게 만들기 위해서는 이 음수 사이클을 계속 방문하는 것이 옳기 때문에 최단경로의 길이는 -INF 로 발산하게 됩니다.

 

이렇게 음수 사이클에 의해 최단 경로가 제대로 정의되지 않을 때를 대비하여 벨만-포드 알고리즘을 사용할 경우에는 음수 사이클을 체크할 수 있는 장치를 만들어 놓습니다.

 

위에서 모든 정점을 V-1 번 방문하면 각 정점별 최단경로가 확정된다고 말씀드렸습니다.

만약 V 번째 방문에서도 최단경로가 갱신이 된다면 음수 사이클이 존재한다고 말할 수 있습니다.

 

이를 알고리즘을 소스코드로 알아보겠습니다.

---

#define MAX 987654321
int V, E,v,e,weight;

vector <pair<int, int> >adj[V_Max];
//메인함수에서 간선을 저장할 벡터를 만들어놓습니다.

vector <int> bellman(int src) {
	vector <int> dist(V, MAX);
    //최단경로의 길이를 저장할 벡터입니다. 초기값은 MAX입니다.
    
	dist[src] = 0;
	//시작점에서 시작점으로의 최단경로는 0으로 설정해둡니다.
    
    bool check;
    //경로가 갱신되었는지 확인하기위한 장치입니다.
    
	for (int iter = 0;iter < V;iter++) {
    //총 (V-1)+1=V 번 방문하게 됩니다. iter=V-1 일 때가 마지막 방문입니다.
    
		check = false;
        //true로 변한다면 갱신에 성공한 것입니다.
        
		for (int here = 0;here < V;here++) {
        //현재 서있는 정점의 위치를 말합니다.
        
			if (dist[here] == MAX) continue; 
            //현재 있는 정점의 최단경로가 아직 갱신전이라면 넘어갑니다.
            
			for (int num = 0;num < (int)adj[here].size();num++) {
            //현재 정점에 인접한 정점을 방문해봅니다.
            
				int there = adj[here][num].first;
                //인접한 정점의 번호
                
				int cost = adj[here][num].second; 
                //인접한 정점으로 가기위한 가중치
                
				if (dist[there] > dist[here] + cost) {
                //인접한 정점으로 방문할 때, 최단경로가 짧아진다면
                
					dist[there] = dist[here] + cost;
                    //경로의 길이를 갱신하고
					check = true;
                    //갱신에 성공했음을 저장합니다.
				}
			}
		}
		if (check == false) break;
        //갱신이 일어나지 않는다면 조기종료합니다.
        //iter=V-1 에서 갱신이 일어나지 않았다면 음수사이클이 없다는 의미입니다.
        
	}
	if (check == true)  dist.clear();
    //iter=V-1 에서 갱신이 일어났다면 true이며 음수사이클이 있다는 의미입니다.
    //따라서 음수사이클이 존재함을 알리기위해 저장한 최단경로를 비워버립니다.
    
	return dist;
}

 

---

벨만-포드 알고리즘의 시간복잡도

각 정점 별로 V번씩 방문하고, 정점에 붙어있는 간선들을 방문하므로 총 시간복잡도는 O(VE) 입니다.

 

벨만-포드 알고리즘와 비슷하면서 시간복잡도가 개선된 알고리즘도 존재합니다.

2020/09/07 - [알고리즘] - SPFA (Shortest Path Faster Algorithm)

---

연습문제

 

2020/08/28 - [백준] - 백준 소스코드 [C++] 11657 타임머신

2020/09/01 - [백준] - 백준 소스코드 [C++] 1865 웜홀

 

최단 경로 알고리즘 중 벨만-포드 알고리즘에 대한 포스팅이었습니다.

오타 지적과 조언은 언제나 환영입니다.