최단거리 알고리즘
그래프에서 가장 짧은 경로를 찾는 알고리즘을 일반적으로 최단거리 알고리즘이라고 합니다.
최단거리 알고리즘은 대표적으로 다익스트라 알고리즘과 플루이드-와샬 알고리즘이 있으며 상황마다 적합한 알고리즘을 사용하는 것이 중요합니다.
플루이드-와샬(Floyd-Warshall) 알고리즘
플루이드-와샬 알고리즘은 모든 정점(node)에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘입니다.
각 노드의 개수 * 2 크기의 최단거리 테이블을 만들고 모든 경우의 수를 고려하여 최단거리 테이블을 갱신하며 최단거리를 계산합니다.
플루이드-와샬 알고리즘의 진행 순서
플루이드-와샬 알고리즘의 로직은 다음과 같습니다.
- 최단 거리 테이블을 Inf(각 노드의 수 * 거리의 최대값보다 큰 값)로 초기화.
- 그래프에서 어떠한 정점을 거치지 않고 다른 정점으로 갈 수 있는 경우를 최단 거리 테이블에 입력.
- 최단거리 테이블에서 자기 자신으로 가는 거리를 0으로 변경.
- 삼중 for문을 사용하여 각 k번째 노드를 거쳐서 한 정점에서 다른 정점으로 갈 수 있는 모든 경우의 수를 고려하여 최단거리 테이블 갱신.
코틀린으로 구현한 플루이드-와샬 알고리즘 예제
fun FloydWarshall(node: Int, graph: Array<IntArray>) {
// 1. 최단거리 테이블을 inf로 초기화.
val res = Array(node) { Array(node) { 1000000 } }
/* 2. 그래프에서 다른 정점을 거치지 않고 바로 갈 수 있는 경우를
* 최단 거리 테이블에 입력.
*/
graph.forEach { arr ->
res[arr[0] - 1][arr[1] - 1] = arr[2]
res[arr[1] - 1][arr[0] - 1] = arr[2]
}
// 3. 최단거리 테이블에서 자기 자신으로 가는 거리를 0으로 변경.
for (i in res.indices) {
for (j in res.indices) {
if (i == j)
res[i][j] = 0
}
}
res.forEach { println(it.toList()) }
/* 4. 삼중 for문을 사용하여 각 k번째 노드를 거쳐서 한 정점에서 다른 정점으로
* 갈 수 있는 모든 경우의 수를 고려하여 최단거리 테이블 갱신.
*/
for (k in res.indices) {
for (i in res.indices) {
for (j in res.indices) {
res[i][j] = min(res[i][j], res[i][k] + res[k][j])
}
}
}
res.forEach { println(it.toList()) }
}플루이드-와샬 알고리즘의 최단거리 경로 복원
위의 플루이드-와샬 알고리즘 예제는 모든 노드에서 다른 모든 노드까지의 최단거리를 구할 수 있지만 그 최단거리가 어떤 경로로 이루어져 있는지는 구할 수 없습니다.
최단거리와 경로 모두를 구하고 싶을때는 어떻게 하면 될까요?
경로를 저장하는 배열을 하나 더 생성해서 각 노드에서 다른 노드로 가는 최단 거리의 경로를 저장해주면 됩니다.
fun FloydWarshall(node: Int, graph: Array<IntArray>) {
// 1. 최단거리 테이블을 inf로 초기화.
val shortestPath = Array(node + 1) { Array(node + 1) { 1000000 } } // 최단거리 테이블
// 1-1. 경로 테이블을 0으로 초기화.
val routeTable = Array(node + 1) { Array(node + 1) { 0 } }
/* 2. 그래프에서 다른 정점을 거치지 않고 바로 갈 수 있는 경우를
* 최단 거리 테이블과 경로 테이블에 입력.
*/
graph.forEach { arr ->
shortestPath[arr[0]][arr[1]] = arr[2]
shortestPath[arr[1]][arr[0]] = arr[2]
routeTable[arr[0]][arr[1]] = arr[1]
routeTable[arr[1]][arr[0]] = arr[0]
}
// 3. 최단거리 테이블에서 자기 자신으로 가는 거리를 0으로 변경.
for (i in 1..node) {
for (j in 1..node) {
if (i == j)
shortestPath[i][j] = 0
}
}
shortestPath.forEach { println(it.toList()) }
println()
routeTable.forEach { println(it.toList()) }
println()
/* 4. 삼중 for문을 사용하여 각 k번째 노드를 거쳐서 한 정점에서 다른 정점으로
* 갈 수 있는 모든 경우의 수를 고려하여 최단거리 테이블과 경로 테이블 갱신.
*/
for (k in 1..node) {
for (i in 1..node) {
for (j in 1..node) {
if (shortestPath[i][j] > shortestPath[i][k] + shortestPath[k][j]) {
routeTable[i][j] = routeTable[i][k]
shortestPath[i][j] = shortestPath[i][k] + shortestPath[k][j]
}
}
}
}
routeTable.forEach { println(it.toList()) }
println()
// routeTable을 이용한 경로 복원. (2->3으로 가는 최단경로는 2->4->3)
var from = 1
var to = 4
for (i in 1..node) {
for (j in 1..node) {
if (from == to) {
print("$from ")
return
}
print("$from ")
from = routeTable[from][to]
}
}
}플루이드-와샬 알고리즘의 시간복잡도
플루이드-와샬 알고리즘은 한 정점과 다른 정점 사이의 최단거리를 k번 반복하며 확인하기 때문에 시간복잡도는 O(n^3)입니다.
다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘은 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘 입니다. 출발 노드에서 현재 선택 가능한 최단 거리를 선택하면서 최단거를 구합니다.
다익스트라 알고리즘의 진행 순서
다익스트라 알고리즘은 아래의 순서로 진행됩니다.
- 최단거리 테이블을 모두 inf로 초기화합니다.
- 노드를 방문했는지 여부를 나타내는 visit배열을 False로 초기화합니다.
- 시작노드의 최단거리를 0으로 설정합니다.
- 최단거리 테이블을 순회하면서 최단거리로 도달할 수 있는 노드를 선택합니다.
- 선택된 노드를 방문 표시하고, 그 노드의 간선들을 순회하며 최단거리 테이블을 갱신합니다.
- 4~5번을 더 이상 선택할 노드가 없을 때까지 반복합니다.
import kotlin.math.min
fun solution() {
val (nodeCnt, edgeCnt) = readln().split(' ').map { it.toInt() }
val start = readln().toInt()
val graph = Array(nodeCnt + 1) { arrayListOf<Pair<Int, Int>>() }
repeat(edgeCnt) {
val input = readln().split(' ').map { it.toInt() }
graph[input[0]] += Pair(input[1], input[2])
}
val dist = Array(nodeCnt + 1) { inf }
// 1. 최단거리 테이블을 모두 inf로 초기화
val fix = Array(nodeCnt + 1) { false }
// 2. 방문 배열을 모두 false로 초기화
// println(graph.contentToString())
dist[start] = 0
// 3. 시작노드의 최단거리를 0으로 설정.
while (true) {
var idx = 0
/*
* 4. 최단거리 테이블을 순회하면서 아직 방문하지
* 않은 최단거리로 도달할 수 있는 노드를 선택합니다.
*/
for (i in 1..nodeCnt) {
if (fix[i])
continue
if (dist[i] < dist[idx])
idx = i
}
if (dist[idx] == inf) // 더이상 선택할 노드가 없을때 종료.
break
/*
* 5. 선택된 노드를 방문 표시하고,
* 그 노드의 간선들을 순회하며 최단거리 테이블을 갱신합니다.
*/
fix[idx] = true
for (edge in graph[idx]) {
// println("curr: ${dist[edge.first]} possible: ${dist[idx] + edge.second}")
dist[edge.first] = min(dist[edge.first], dist[idx] + edge.second)
/*
* 선택된 노드와 연결된 모든 노드의 현재 최단거리와 갱신할 수 있는 거리를 비교하여 더 짧은 것을 최단거리 배열에 기록
*/
}
// 6. 4~5번을 더 이상 선택할 노드가 없을 때까지 반복합니다.
}
printAnswer(dist)
}다익스트라 알고리즘의 시간복잡도
위의 구현은 시간복잡도가 O(n^2)입니다. 하지만 우선순위큐를 사용하면 O(nlogn)으로 최적화 할 수 있습니다.
우선순위 큐를 사용한 최적화
다익스트라 알고리즘에서 최단거리 테이블을 순회하면서 아직 방문하지 않은 최단거리 노드를 구하는 로직을 우선순위큐를 이용하여 더 빠르게 만들 수 있습니다.
우선순위큐를 사용하지 않으면 최단거리 테이블의 최솟값을 찾느라 매번 테이블을 순회해야 하지만 우선순위큐를 사용하면 매번 테이블 전체를 순회할 필요가 없어집니다.
fun solution() {
val (nodeCnt, edgeCnt) = readln().split(' ').map { it.toInt() }
val start = readln().toInt()
val graph = Array(nodeCnt + 1) { arrayListOf<Pair<Int, Int>>() }
repeat(edgeCnt) {
val input = readln().split(' ').map { it.toInt() }
graph[input[0]] += Pair(input[1], input[2])
}
val dist = Array(nodeCnt + 1) { inf }
// 1. 최단거리 테이블을 모두 inf로 초기화
// println(graph.contentToString())
dist[start] = 0
// 3. 시작노드의 최단거리를 0으로 설정.
val heap = PriorityQueue { a: Pair<Int, Int>, b: Pair<Int, Int> ->
if (a.first > b.first) 1 else if (a.first == b.first) 0 else -1
}
heap += Pair(0, start)
while (heap.isNotEmpty()) {
val (distance, node) = heap.poll()
/*
* 4. 최단거리 테이블을 순회하면서 아직 방문하지
* 않은 최단거리로 도달할 수 있는 노드를 선택합니다.
*/
if (dist[node] != distance)
continue
/*
* 5. 선택된 노드를 방문 표시하고,
* 그 노드의 간선들을 순회하며 최단거리 테이블을 갱신합니다.
*/
for (edge in graph[node]) {
if (dist[edge.first] > dist[node] + edge.second) {
dist[edge.first] = dist[node] + edge.second
heap += Pair(dist[edge.first], edge.first)
}
}
// 6. 4~5번을 더 이상 선택할 노드가 없을 때까지 반복합니다.
}
printAnswer(dist)
}
우선순위큐를 사용하면 방문 배열도 필요가 없어집니다. 우선순위 큐에 들어가 있는 거리와 최단거리 테이블에 기록된 거리를 비교하여 그 값이 다르면 최단 거리 테이블 갱신 이전의 기록이므로 무시하면 되기 때문입니다.
수신제가치국평천하