-
[알고리즘/벨만포드] 벨만-포드(Bellman-Ford) 알고리즘Mhwan's Study/Algorithms 2021. 1. 23. 03:12
벨만-포드 알고리즘은 이전에 한 다익스트라 알고리즘처럼 단일 시작점에서 모든 정점까지의 최단거리를 구하는 알고리즘입니다.
이 알고리즘은 다익스트라와 달리 가중치가 음수인 간선을 포함하는 그래프에서 최단 경로를 정확히 구할 수 있고, 음수인 사이클을 판별해낼 수 있습니다. 다익스트라 알고리즘에 비해 시간복잡도가 좋지 않으므로, 음수인 간선을 갖는 그래프나 음수인 사이클을 판별할 때 사용하는 것이 좋습니다.
# 완화 (Relaxation)
이 알고리즘의 가장 핵심이 되는 특성입니다. u에서 v까지의 최단거리 dis[v] <= dis[u] + u에서 v 간선의 가중치가 항상 참이라는 것입니다. 사실 이 완화과정은 이미 다익스트라 알고리즘에서도 했었는데, 해당 노드에서 인접한 노드에 방문할 때 dis[nextNode.v] > cur.weight + nextNode.weight이 만족할 경우에만 우선순위 큐에 넣었습니다.
1234567for (Node nextNode : graph.sparseList.get(current.v)) {int newDis = current.weight + nextNode.weight;if (dis[nextNode.v] > newDis) {dis[nextNode.v] = newDis;}}cs 즉, 다음에 방문할 v까지의 최단거리는 u까지 오는 최단거리에서 u에서 v를 가는데 필요한 비용보다 같거나 작다라는 말입니다. 다익스트라 알고리즘에서도 다음에 방문할 v가 더 클 경우 갱신하는 모습을 위에 코드에서 볼 수 있죠.
이렇게 벨만-포드 알고리즘에서는 해당 노드까지 가는 최대 상한값을 가진 upper[]로 시작해서, 모든 간선에 upper[v] > upper[u] + weight가 만족할 때 upper[v] = upper[u] + weight을 하는 완화작업을 반복적으로 실행합니다. 이렇게 되면 upper는 점점 줄어들고 실제 우리가 구하고자하는 최단거리를 구할 수 있게 됩니다.
이제 완화작업을 최대 몇번해야 최단거리를 찾을 수 있을지를 생각해보겠습니다. 음수 사이클이 없는 그래프에서 최단 경로는 한 정점을 두번 이상 지나는 일이 없습니다. 그렇다면 최단 경로는 최대 V개의 정점을 갖게 되고, V-1개의 간선을 갖게 되므로 모든 간선에 대한 완화작업은 최대 V-1번이면 충분합니다.
# 소스코드
이 소스코드의 예시 그래프는 이전 다익스트라 포스팅에서 다룬 것과 동일합니다.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110=import java.io.IOException;import java.util.*;public class Main {public static void main(String[] args) throws IOException {int N = 7;Graph graph = new Graph(N);graph.addEdge(1, 2, 5);graph.addEdge(1, 3, 1);graph.addEdge(3, 4, 2);graph.addEdge(4, 5, 5);graph.addEdge(4, 2, 1);graph.addEdge(4, 7, 3);graph.addEdge(2, 6, 3);graph.addEdge(2, 7, 3);graph.addEdge(6, 7, 2);bellmanFord(graph, N, 1);}private static void bellmanFord(Graph graph, int N, int start) {int[] upper = new int[N+1];//스패닝 트리를 위한 배열int[] parent = new int[N+1];Arrays.fill(upper, Integer.MAX_VALUE);upper[start] = 0;parent[start] = start;boolean isUpdate = false;//for문의 loop횟수는 N-1번, 1번 더 반복면 음수 사이클이 있는지 확인할 수 있음for (int i = 0; i < N-1; i++) {isUpdate = false;//모든 간선에 대한 완화작업for (int cur = 1; cur <= N; cur++) {for (Node next : graph.sparseList.get(cur)) {//현재의 노드의 upper가 상한 값이면 갱신 불가능if (upper[cur] != Integer.MAX_VALUE) {int nextCost = upper[cur] + next.weight;if (upper[next.v] > nextCost) {upper[next.v] = nextCost;//스패닝 트리에 기록parent[next.v] = cur;isUpdate = true;}}}}//모든 간선에 대해 완화가 완료되었으므로 종료if (!isUpdate)break;}System.out.println(Arrays.toString(upper));System.out.println(Arrays.toString(parent));}private static void findRoot(int v, int start, int[] parent) {int finish = v;StringBuilder sb = new StringBuilder();while (v != start) {sb.insert(0, " -> "+v);v = parent[v];}sb.insert(0, start);System.out.println(finish +" : "+sb.toString());}public static class Node implements Comparable<Node>{int v;int weight;public Node(int v, int weight) {this.v = v;this.weight = weight;}@Overridepublic int compareTo(Node o) {return Integer.compare(weight, o.weight);}}public static class Graph {int n;List<List<Node>> sparseList;public Graph(int n) {this.n = n;this.sparseList = new ArrayList<>();for (int i=0; i< n+1; i++)sparseList.add(new ArrayList<>());}/*** 양쪽으로 연결*/public void addEdge(int u, int v, int w){sparseList.get(u).add(new Node(v, w));sparseList.get(v).add(new Node(u, w));}//한쪽으로 연결public void addEdgeSingle(int u, int v, int w) {sparseList.get(u).add(new Node(v, w));}}}cs 이 코드의 결과값을 보기 위해 upper 배열을 출력시키면 각 노드까지 가는데 최단거리가 정확히 계산된 것이 보입니다.
물론 이 예시 그래프는 음수인 간선을 포함하고 있지 않지만, 음수인 간선에서도 정확히 작동합니다.
# 음수인 사이클의 판별
벨만 포드 알고리즘을 통해 음수인 사이클의 판별할 수 있다고 했습니다. 음수인 사이클의 특징은 위 그래프와 같이 1 -> 2 -> 3까지 가는 가중치의 합이 -2로 0보다 작아 이 사이클을 돌면 돌수록 가중치는 더욱 작아질 것입니다. 그래프에서 이런 사이클이 있는지 판단은 간단합니다. 음수인 사이클이 있으면 매번 완화작업을 시도할 때 항상 한번은 성공을 하게 될 것입니다. 그렇다면 위에서 V-1개의 루프만큼 완화작업을 한 뒤 한번 더인 V번째의 완화작업을 했을 때도 완화는 성공하는 것이죠. 이는 위의 코드에서 단 두줄의 코드 수정이면 충분합니다.
123456789101112131415161718192021222324252627282930313233private static boolean hasNegativeCycle(Graph graph, int N, int start) {int[] upper = new int[N+1];Arrays.fill(upper, Integer.MAX_VALUE);upper[start] = 0;boolean isUpdate = false;//for문의 loop횟수는 N번, 1번 더 반복면 음수 사이클이 있는지 확인할 수 있음for (int i = 0; i < N; i++) {isUpdate = false;//모든 간선에 대한 완화작업for (int cur = 1; cur <= N; cur++) {for (Node next : graph.sparseList.get(cur)) {//현재의 노드의 upper가 상한 값이면 갱신 불가능if (upper[cur] != Integer.MAX_VALUE) {int nextCost = upper[cur] + next.weight;if (upper[next.v] > nextCost) {upper[next.v] = nextCost;isUpdate = true;}}}}//모든 간선에 대해 완화가 완료되었으므로 종료if (!isUpdate)break;}//완화작업에 성공했다면 isUpdate는 true를 갖게 되고, 이 말은 음수인 사이클이 있다는 것임return isUpdate;}cs # 시간복잡도
한번의 완화작업은 모든 간선을 살펴보게 되므로 O(E), 이것을 V번 만큼 반복수행하므로, O(VE)라는 시간복잡도를 갖게 됩니다.
'Mhwan's Study > Algorithms' 카테고리의 다른 글
[알고리즘/토끼와 거북이] 플로이드의 토끼와 거북이 (Floyd's Tortoise and Hare) 알고리즘 (0) 2021.04.16 [알고리즘/플로이드] 플로이드-와샬(Floyd-Warshall) 알고리즘 (0) 2021.02.12 [알고리즘/다익스트라] 다익스트라(Dijkstra) 알고리즘 (0) 2021.01.15 [알고리즘/투 포인터] 2020 카카오 인턴십 - 보석 쇼핑 (0) 2021.01.06 [알고리즘/투포인터] 투포인터 알고리즘 (0) 2021.01.06