Algorithms
15. 그래프 최단경로(다익스트라, 벨만-포드)
조슈아。
2024. 6. 11. 00:30
반응형
최단경로(shortest path) 문제
네트워크에서 정점 u 와 정점 v 를 연결하는 경로 중에서 간선들의 가중치 합이 최소가되는 경로를 찾는 문제
- 가중치 : 거리, 비용, 시간 등
- 가중치가 없는 그래프 : 간선의 개수가 가장 적은 경로가 최단경로
- 가중치가 있는 그래프 : 시작노드에서 마지막 노드까지 이동할 때 거치는 간선의 가중치의 총합이 최소가 되는 것.
다익스트라 알고리즘(Dijkstra algorithm)
네트워크에서 하나의 시작정점에서 모든 다른 정점까지의 최단경로를 찾는 알고리즘
- 가중치가 있는 알고리즘은 대부분 다익스트라 알고리즘을 사용한다고 보면된다.
- 다익스트라 알고리즘은 양의 가중치만 있는 그래프에서만 동작하므로 음의 가중치가 있는 그래프에서 제대로 동작하지 않는다.
- 다익스트라 알고리즘은 한 번 방문한 노드는 다시 방문하지 않는다. 그러므로 음의 가중치가 있는 그래프에서는 제대로 작동하지 않는것.
- 시작노드를 설정하고 시작 노드부터 특정 노드까지 최소 비용을 저장할 공간과 직전노드를 저장할 공간을 마련한다.
- 최소비용을 저장할 공간은 모두 매우 큰 값(무한대 INF 표현)으로 초기화
- 시작노드의 최소 비용은 0이고 직전 노드는 자신으로 설정
- 해당 노드를 통해 방문할 수 있는 노드(아직 방문하지 않은 노드) 중 현재까지 구한 최소 비용이 가작 적은 노드를 선택
- 해당 노드를 거쳐 각 노드까지 가는 최소 비용과 현재가지 구한 최소 비용을 비교하여 작은 값을 각 노드의 최소비용으로 갱신
- 이때 직전 노드도 같이 갱신
- 노드의 개수에서 1을 뺀 만큼 반복
//입력 : 가중치 그래프 G, 가중치는 음수가 아님
//출력 : 출력 distance 배열, distance[u]는 v에서 u까지의 최단 거리이다.
//Big O (n^2)
shortest_path(G, v)
s ← {v}
for 각 정점 w ⊆ G do
distance[w] <- weight[v][w];
while 모든 정점이 S에 포함되지 않으면 do
u <- 집합 S에 속하지 않는 정점 중에서 최소 distance 정점;
S <- S ∪ {u}
for u에 인접하지 않고 S에 인접하지 않는 각 정점 z do
if distance[u] + weight[u][z] < distance[z]
then distance[z] <- distance[u] + weight[u][z]
알고리즘 절차
1. 시작노드 A의 최소비용은 0 직전노드는 A로 초기화
2. 방문하지 않은 노드 중 최소비용이 가장 적은 A노드를 선택
- 해당 노드를 거쳐 각 노드까지 가는 비용과 기존에 구한 각 노드의 최소 비용을 비교
- A 노드에서 {B, C, E}의 가중치는 각각 {4, 4, 1}
- 현재까지 해당 노드의 최소 비용은 INF이므로 B의 최소비용은 4, C의 최소비용은 4, E의 최소비용은 1로 갱신
3. 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 E를 선택
- 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인.
- 노드 C의 현재 비용은 4, E를 거쳤을 때의 비용은 E의 최소비용(1)과 E → C의 가중치(2)를 합친 값 3
- 현재까지 구한 최소 비용보다 값이 더 작으므로 C의 최소비용3, 직전노드 E 로 수정
4.방문하지 않은 노드 중 최소비용이 가장 적은 노드 C를 선택
- 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인
- 노드 D의 경우 기존 최소비용이 INF(경로 없음)이지만, C를 거치면 최소비용(3) + C → D 의 가중치(8)을 합쳐 11이 되어 INF보다 작다.
- 그러므로 D는 최소비용 11, 직전노드 C로 갱신
5. 방문하지 않은 노드 중 최소비용이 가장 적은 노드 B를 선택
- 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인
- 확인 할 필요가 없으므로 건너뜀(갱신 없음)
6. 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 D를 방문
- 확인 할 필요가 없으므로 건너뜀(갱신 없음)
import java.util.*;
public class DijkstraAlgorithm {
public static void main(String[] args) {
Solution sol = new Solution();
int[] result = sol.solution(new int[][] {
{0,1,9},
{0,2,3},
{1,0,5},
{2,1,1}
}, 0, 3);
System.out.println(Arrays.toString(result));
int[] result2 = sol.solution(new int[][] {
{0,1,1},
{1,2,5},
{2,3,1}
}, 0, 4);
System.out.println(Arrays.toString(result2));
}
private static class Solution {
public int[] solution(int[][] graph, int start, int n) {
return dijkstra(start, n, initAdjList(graph, n));
}
private List<List<Node>> initAdjList(int[][] graph, int n) {
List<List<Node>> adjList = new ArrayList<>(n);
//인접리스트 초기화
for (int i = 0; i < n; i ++) {
adjList.add(new ArrayList<>());
}
//graph 정보 인접 리스트로 저장(단방향)
for (int[] edge : graph) {
adjList.get(edge[0]).add(new Node(edge[1], edge[2]));
}
return adjList;
}
private int[] dijkstra(int start, int n, List<List<Node>> adjList) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE); //INF 로 초기화
//시작 위치 0으로 초기화
dist[start] = 0;
//우선순위 큐를 생성하고 시작 노드를 삽입
PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost));
priorityQueue.add(new Node(start, 0));
while(!priorityQueue.isEmpty()) {
//거리가 가장 짧은 노드를 dequeue
Node now = priorityQueue.poll();
//현재노드의 거리 값이 큐에서 거리 값보다 크면, 해당 노드는 이미 방문한 것으로 무시
if (dist[now.dest] < now.cost) {
continue;
}
//현재 노드와 인접한 노드들의 거리 값을 계산하여 업데이트
for (Node next : adjList.get(now.dest)) {
//기존에 발견했던 거리보다 더 짧은 거리를 발견했다면 거리 값을 갱신하고 큐에 넣음
if (dist[next.dest] > now.cost + next.cost) {
dist[next.dest] = now.cost + next.cost;
priorityQueue.add(new Node(next.dest, dist[next.dest]));
}
}
}
return dist;
}
private static class Node {
int dest;
int cost;
public Node(int dest, int cost) {
this.dest = dest;
this.cost = cost;
}
}
}
}벨만-포드 알고리즘(Bellman-ford Algorithm)
- 다익스트라 알고리즘과 마찬가지로 노드에서 노드까지의 최소 비용을 구하는 알고리즘으로, 매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용을 갱신하므로 음의 가중치를 가지는 그래프에서도 최단경로를 구할 수 있다.
- 간선의 가중치가 음수인 일반적인 경우 단일 출발지 최단 경로 문제를 해결
- 가중 방향 그래프 G= (V,E)가 출발점 s와 가중함수 w : E → R 과 함께 주어졌을 때 벨만-포드 알고리즘은 출발점으로부터 도달 가능한 음의 가중치를 갖는 순한이 있는지를 나타내는 논리값을 리턴
- 시작 노드를 설정한 다음 시작 노드의 최소비용은 0, 나머지 노드는 INF로 초기화
- 이후 최소비용을 갱신할 때마다 직전노드도 갱신
- 노드의 개수 - 1만큼 연산을 반복
- 시작노드에서 갈 수 있는 각 노드에 대해 전체 노드 각각을 거쳐갈 때 현재까지 구한 최소 비용보다 더 적은 최소 비용이 있는지 확인하여 갱신
- 최소비용을 갱신할 때 V의 직전 노드 값도 같이 갱신
- 과정 2를 마지막으로 한번 더 수행하여 갱신되는 최소 비용이 있는지 확인.
- 만약 있다면 음의 순환이 있음을 의미
bellman_ford(G, w, s)
initialize_single_source(G,s)
for i = 1 to | G.V | - 1
for 각 간선(u, v) <= G.E
RELAX(u,v,w)
for 각 간선(u,v) <= G.E
if v.d > u.d + w(u.v)
return FALSE
return TRUE
알고리즘 절차
1. 시작노드 A 기준 최소비용 0, 직전노드 0, 나머지 노드 INF로 초기화
2. 노드 A에서 A를 거쳐 각 노드 {B, C, E}까지 가는 비용중 현재까지 구한 최소 비용보다 적은 값이 있는지 확인하고 현재까지 구한 최소비용보다 적으면 갱신 (간선이 없다면 INF로 계산한다는 것을 주의)
- 최소비용(A)(0) == 최소비용(A)(0) + 간선(A, A)(0) : 갱신하지 않음
- 최소비용(B)(INF) > 최소비용(A)(0) + 간선(A, B)(4) : 최소비용(B)를 INF에서 4로 갱신
- 최소비용(C)(INF) > 최소비용(A)(0) + 간선(A, C)(3) : 최소비용(C)를 INF에서 3로 갱신
- 최소비용(D)(INF) == 최소비용(A)(0) + 간선(A, D)(INF) : 갱신하지 않음
- 최소비용(E)(INF) > 최소비용(A)(0) + 간선(A, E)(-6) : 최소비용(E)를 INF에서 -6로 갱신
3. 노드 A에서 B를 거쳐 각 노드 {D}까지 가는 비용중 현재까지 구한 최소 비용보다 적은 값이 있는지 확인하고 현재까지 구한 최소비용보다 적으면 갱신
- 최소비용(A)(0) < 최소비용(B)(4) + 간선(B, A)(INF) : 갱신하지 않음
- 최소비용(B)(4) == 최소비용(B)(4) + 간선(B, B)(0) : 갱신하지 않음
- 최소비용(C)(3) < 최소비용(B)(4) + 간선(B, C)(INF) : 갱신하지 않음
- 최소비용(D)(INF) > 최소비용(B)(4) + 간선(B, D)(5) : 9로 갱신
- 최소비용(E)(-6) < 최소비용(B)(4) + 간선(B, E)(-6) : 갱신하지 않음
4. 노드 A에서 C를 거쳐 각 노드 {B}까지 가는 비용중 현재까지 구한 최소 비용보다 적은 값이 있는지 확인하고 현재까지 구한 최소비용보다 적으면 갱신 (C를 거쳐 B로 가는 새 경로(5)는 기존 B(4)의 최소 비용보다 크므로 갱신 X)
- 최소비용(A)(0) < 최소비용(C)(3) + 간선(C, A)(INF) : 갱신하지 않음
- 최소비용(B)(4) < 최소비용(C)(3) + 간선(C, B)(2) : 갱신하지 않음
- 최소비용(C)(3) == 최소비용(C)(3) + 간선(C, C)(0) : 갱신하지 않음
- 최소비용(D)(9) > 최소비용(C)(3) + 간선(C, D)(INF) : 갱신하지 않음
- 최소비용(E)(-6) < 최소비용(C)(3) + 간선(C, E)(INF) : 갱신하지 않음
5. 노드 A에서 D를 거쳐서 가는 방법은 없으므로 갱신하지 않음
6. 노드 A에서 E를 거쳐 각 노드까지 가는 최소비용을 갱신. 모든 최단 경로에 대해 노드의 최소비용을 체크했으므로, 벨만-포드 알고리즘의 첫번째 반복이 끝난다.
- 최소비용(A)(0) < 최소비용(E)(-6) + 간선(E, A)(INF) : 갱신하지 않음
- 최소비용(B)(4) < 최소비용(E)(-6) + 간선(E, B)(INF) : 갱신하지 않음
- 최소비용(C)(3) > 최소비용(E)(-6) + 간선(E, C)(2) : -4로 갱신
- 최소비용(D)(9) > 최소비용(E)(-6) + 간선(E, D)(INF) : 갱신하지 않음
- 최소비용(E)(-6) < 최소비용(E)(-6) + 간선(E, E)(0) : 갱신하지 않음
- 위해서 했던 과정을 노드개수 -1 번 반복하므로 1~6단계를 4번 더 반복
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BellManFord {
public static void main(String[] args) {
Solution sol = new Solution();
int[] result = sol.solution(new int[][] {
{1,2,7},
{1,3,5},
{1,4,3},
{3,4,3},
{3,5,3},
{4,2,3},
{4,5,-6},
{5,3,2},
}, 1, 7);
System.out.println(Arrays.toString(result));
int[] result2 = sol.solution2(new int[][] {
{1,2,7},
{1,3,5},
{1,4,3},
{3,4,3},
{3,5,3},
{4,2,3},
{4,5,-6},
{5,3,2},
}, 1, 7);
System.out.println(Arrays.toString(result2));
}
private static class Solution {
private static final int INF = Integer.MAX_VALUE;
public int[] solution(int[][] graph, int start, int n) {
List<List<Node>> adjList = initAdjList(graph, n);
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[start] = 0;
//정점 수 만큼 반복
for (int v = 1; v <= n; v++) {
//모든 간선을 순회
for (Node node : adjList.get(v)) {
if (dist[node.from] == INF) {
continue;
}
if (dist[node.to] > dist[node.from] + node.cost) {
dist[node.to] = dist[node.from] + node.cost;
}
}
}
return dist;
}
private int[] solution2(int[][] graph, int start, int n) {
List<List<Node>> adjList = initAdjList(graph, n);
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[start] = 0;
//정점 수 만큼 반복
for (int v = 1; v <= n; v++) {
//모든 간선을 순회
for (Node node : adjList.get(v)) {
if (dist[node.from] != INF) {
dist[node.to] = Math.min(dist[node.to], dist[node.from] + node.cost);
}
}
}
return dist;
}
private List<List<Node>> initAdjList(int[][] graph, int n) {
List<List<Node>> adjList = new ArrayList<>();
for (int i = 0; i <= n; i ++) {
adjList.add(new ArrayList<>());
}
for (int[] edge : graph) {
adjList.get(edge[0]).add(new Node(edge[0], edge[1], edge[2]));
}
return adjList;
}
private static class Node {
int from;
int to;
int cost;
public Node(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
}
}
}
다익스트라 알고리즘, 벨만 포드 알고리즘 차이
| 목적 | 장 단점 및 특성 | 시간 복잡도 | |
| 다익스트라 알고리즘 |
출발 노드부터 도착 노드들까지의 최단 경로 찾기 | 음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 없다(그리디 방식) | O(V^2), 우선순위 큐로 개선하면 O(E*logV) |
| 벨만-포드 알고리즘 |
출발 노드부터 도착노드들까지의 최단 경로 찾기 | 음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 있고, 음의 순환도 감지할 수 있다. | O(V*E) |
References
C 언어로 쉽게 풀어쓴 자료 구조
코딩 테스트 완전 전복
Interotuction to algorithms
반응형