다익스트라, 플로이드-워셜
이번 글에서 정리해볼 내용은 다익스트라 알고리즘과 플로이드-워셜 알고리즘이다. 이 두 알고리즘은 그래프에서의 최소 "비용"을 알아내기 위해서 사용한다. 아래 여러 목차들을 통해 이 말이 무엇인지 자세히 알아보자.
간선의 가중치
그래프는 간단히 정점(노드, node)와 간선(엣지, edge)로 이루어져 있다. 가장 간단한 그래프의 형식이라면 앞서 말한 노드와 엣지 자체의 존재만 고려하면 될 것이다. 허나 많은 경우 여기에 가중치라는 개념이 추가된다. 가중치는 쉽게 말해 비용이다. A와 B를 이어주는 a 라는 간선이 있을 때, 이 a라는 간선이 k라는 가중치를 가질 수 있는 것이다. 이 경우 A->B로 갈 때 k라는 비용이 필요하게 된다. 이 개념을 인지하고 나서 다음 내용을 보자.
최단 거리
그래프는 어떻게 보면 현실 세계를 나타낼 수 있는 구조이기도 하다. 단순히 Node들을 도시, Edge 들을 도로로 볼 경우 각 도시들 사이의 거리는 해당 도시들을 잇는 도로(Edge)의 가중치가 될 것이다. 조금 감이 오는가?
이때 서울에서 부산까지의 최단 거리를 구해야 한다고 생각해보자. 서울에서 부산까지 가는 경로는 아주 많을 것이다. 많은 노드와 엣지들을 지나게 될 것 이고, 각 경로마다 거리도 다를 것이기에 우리는 그 중 가장 짧은 거리를 찾기 위해서 가중치를 모두 더해서 그 합을 비교해야 할 것이다. 자 이것이 그래프에서 마주할 수 있는 최소 비용(거리, 등 등) 문제이다. 이번 글에서 알아보고자 하는 두 가지의 알고리즘이 바로 이런 그래프의 최단 거리, 최소 비용 문제에서 사용하는 알고리즘이다.
다익스트라
다익스트라 알고리즘, Dijkstra는 다이나믹 프로그래밍(DP)를 활용한 "최단 경로 탐색 알고리즘"이다. 여기서 DP는 간단히 말해 특정 작은 문제에 대해 값을 구해놓고 활용하는 방법~ 정도로 이해해두자. 결국 이 알고리즘이 DP인 이유는 최단거리란 여러 개의 최단 거리로 이루어져 있기 때문이다. 작은 문제로 나눠서 해결할 수 있기 때문에 DP의 특징을 살릴 수 있는 것이다.
이 다익스트라 알고리즘의 특징은 다음과 같다.
- 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로(비용)을 알려준다.
- 이 때 음의 간선을 포함할 수 없다.(가중치 == 비용 이 음수 값인 간선)
참고 : https://m.blog.naver.com/ndb796/221234424646
구현
실제로 다익스트라 알고리즘을 구현한다면 다음과 같은 순서를 가져야 한다.
- root node를 설정한다.
- root node의 인접 노드에 최소 비용을 업데이트 한다.
- 방문하지 않은 node들 중 가장 비용이 작은 노드를 선택하고 이동한다.
- 해당 node의 인접 노드의 최소 비용을 업데이트 한다.
- 만약 인접 노드의 비용을 업데이트 했는데 해당 노드를 아직 방문하지 않았다면 방문해야할 목록에 추가한다.(코드적 구현)
- 모든 node를 방문할 때 까지 3~5를 반복한다.
// 인접 node map이 구현되어 있다고 가정하자.
// value인 IntArray는 key에서 해당 array의 index까지의 비용이 적혀있다. 연결되어 있지 않을 경우 0 이다.
adjs = HashMap<Int, IntArray>()
fun dijkstra(adjs: HashMap<Int, IntArray>, start: Int, n: Int): IntArray {
val dist = IntArray(n, {100000*n})
val visited = BooleanArray(n)
val queue = PriorityQueue<Pair<Int, Int>>({a,b -> a.second-b.second})
queue.offer(Pair(start, 0))
while (queue.isNotEmpty()) {
val now = queue.poll()
if (!visited[now.first-1]) visited[now.first-1] = true
for (i in 1..n) {
var next = adjs.getValue(now.first)[i-1] //현재부터 i까지의 거리\
if (next != 0) {
if (dist[i-1] > now.second+next) {
dist[i-1] = now.second+next
if (!visited[i-1]) {
queue.offer(Pair(i, dist[i-1]))
}
}
}
}
}
dist[start-1] = 0
return dist
}해당 코드를 읽어보면 이해가 될 것이다.
Time-complexity
방문하지 않은 노드들 중 최단 거리를 구하는 데에 있어 선형 탐색을 사용할 경우 O(n^2)이 되고, 위 코드와 같이 heap 자료구조 형 중 하나인 PriorityQueue를 활용할 경우 O(nlogn)으로 줄일 수 있다.
플로이드-워셜
Floyd-Warshall 알고리즘의 경우 다익스트라 알고리즘의 확장형(?) 이라고 할 수 있을 지도 모른다. 노드 까지의 최단 거리를 구한다는 목적 자체느 비슷할 수 있으나 플로이드-워셜 알고리즈만의 특징들이 있다.
- 플로이드-워셜 알고리즘은 모든 노드간의 최단 비용(경로)를 구할 수 있다. 다익스트라가 임의의 노드로 부터 모든 노드까지 였다면, 플로이드-워셜은 전체에 대해서 이를 구한다.
- 플로이드-워셜의 경우 음의 간선(edge)에서도 사용할 수 있다.
구현
이를 구현하기 위해선 우선 인접 노드 비용 배열을 구해야 한다. 이때 map 형태가 아닌 정말 행렬(이중 array?)의 형태로 나타내는 것을 추천한다. 또 그 상태에서 서로 인접하지 않은 node까지의 비용은 아주 큰 값(최대 비용보다 클 값)으로 설정해야 한다. 또 자기 자신으로의 비용은 0으로 한다. 이러한 초기 셋팅 후 과정은 다음과 같다.
- 특정 노드 i를 선택한다.
- 노드 i를 중간 노드로 하여 a -> b로 가는 비용을 업데이트 한다.
이를 좀더 자세히 설명하자면 기존의 a->b로 가는 비용과 a->i + i->b로 가는 비용을 비교하여 더 작은 것으로 업데이트 한다. - 1~2의 과정을 모든 노드(i, 1~n)에 대해서 반복한다.
이를 코드로 살펴보자
// 최종적으로 만들고자 하는 행렬의 초기화
// 기본적으로 모든 비용을 매우 큰 값으로 설정한다.(해당 값은 특정 문제의 조건임으로 의미를 갖지 말아라.
val dists = Array<IntArray>(n, {IntArray(n, {100000 * n})})
// fares는 노드간의 연결을 의미한다. [노드a, 노드b, 비용]의 형태를 갖는다.
for (edge in fares) {
dists[edge[0]-1][edge[1]-1] = edge[2]
dists[edge[1]-1][edge[0]-1] = edge[2]
}
// 자기로의 거리는 0으로 나타낸다.
for (i in 0..n-1) {
dists[i][i] = 0
}
// 모든 노드에 대해서 중간 노드가 되는 것을 고려하고
for (k in 0..n-1) {
// 두번의 for문을 통해서 모든 케이스에 대해 체크 한다.
for (i in 0..n-1) {
for (j in 0..n-1) {
dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])
}
}
}위와 같이 dists를 모두 업데이트 하고 나면 dist[i][j]가 i 노드에서 j 노드로 가는 최단 비용(거리)가 된다.
Time-complexity
위 코드에서 살펴볼 수 있듯, O(n^3)인 아주 무거운 시간 복잡도를 가지고 있다. 따라서 n이 너무 크지 않은 경우에만 활용할 수 있다.
활용
이 두 알고리즘 모두 그래프에서 활용할 수 있다. 다만 활용 조건이 좀 다르다는 것만 다시 한번 기억하고 가자.
- 시작 노드가 정해져 있는 상태에서 특정 노드 까지의 거리 1개만 확정적으로 구하면 되는 경우에는 다익스트라를 사용한다.
- 시작노드가 정해져 있지 않은 많은 경우를 고려해야 한다면 플로이드-워셜 알고리즘을 쓴다. 다만 이때 그래프의 사이즈를 한번 생각해보자.
