최단거리 알고리즘 - 플로이드 와샬(Floyd-Warshall) feat.kotlin

컴퓨터 과학에서 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다

 

"모든 노드"에서 다른 "모든 노드"까지 최단경로 모두 계산

 

모든 정점 하나하나 마다 거쳐갈때 상황을 가정하여, 최단거리를 완화해서 나간다는 점에서 dp 유형에 해당하는 알고리즘이다.

 

노드 k를 경유해 가는 경우를 확인
(A --> B) 와 (A --> K --> B) 뭐가 더 짧은지 확인한다.

 

 

예시) 

 

k = 1 일때,

 

4번  --> 2번 이동 불가능(INF) 했지만, 1을 경유하면,  4 --> 1 --> 2  값 5로 갱신

4번  --> 5번 이동 불가능(INF) 했지만, 1을 경우하면,  4 --> 1 --> 5  값 -2로 갱신

 

새롭게 갱신된 그래프를 통해, k = 2 일때,

 

1번  -->  4번 이동 불가능(INF) 했지만, 2을 경유하면,  1 --> 2 --> 4  값 4로 갱신

3번  --> 4번 이동 불가능(INF) 했지만, 2을 경유하면,  3 --> 2 --> 5  값 5로 갱신

3번  --> 5번 이동 불가능(INF) 했지만, 2을 경유하면,  3 --> 2 --> 5  값 11로 갱신

 

새롭게 갱신된 그래프를 통해, k = 3 일때,

 

4번  -->  2번 5의 비용을 소모 했지만, 3을 경유하면,  4 --> 3 --> 2  값 -1로 갱신

 

새롭게 갱신된 그래프를 통해, k = 4 일때,

 

1번  --> 3번 8의 비용을 소모 했지만, 4을 경유하면,  1 --> 4 --> 3  값 -1로 갱신

2번  --> 1번 이동 불가능(INF)했지만, 4을 경유하면,  2--> 4 --> 1  값 3로 갱신

2번  --> 3번 이동 불가능(INF)했지만, 4을 경유하면,  2 --> 4 --> 3 값 -4로 갱신

2번  --> 5번 7의 비용을 소모 했지만, 4을 경유하면,  2 --> 4 --> 5  값 -1로 갱신
3번  --> 1번 이동 불가능(INF)했지만, 4을 경유하면, 3 --> 4 --> 1  값 7로 갱신
3번  --> 5번 11의 비용을 소모 했지만, 4을 경유하면, 3 --> 4 --> 5  값 3로 갱신
5번  --> 1번 이동 불가능(INF)했지만,  4을 경유하면, 5 --> 4 --> 1  값 8로 갱신
5번  --> 2번 이동 불가능(INF)했지만,  4을 경유하면, 5 --> 4 --> 2  값 5로 갱신
5번  --> 3번 이동 불가능(INF)했지만,  4을 경유하면, 5 --> 4 --> 3  값 1로 갱신

 

새롭게 갱신된 그래프를 통해, k = 5 일때,

 

1번  --> 2번 3의 비용을 소모 했지만, 4을 경유하면,  1 --> 5 --> 2  값 1로 갱신

1번  --> 3번 -1의 비용을 소모 했지만, 4을 경유하면,  1 --> 5 --> 3  값 -3로 갱신

1번  --> 4번 4의 비용을 소모 했지만, 4을 경유하면,  1 --> 5 --> 4 값 2로 갱신

@	1	2	3	4	5
1	0	1	-3	2	-4
2	3	0	-4	1	-1
3	7	4	0	5	3
4	2	-1	-5	0	-2
5	8	5	1	6	0

 

실제 문제를 해결하는 순서.

 

정점의 개수가 500개를 넘어가지 않는지 확인한다

 

1. 입력값을 통해 인접행렬(가중치 행렬)을 생성한다.

- 인접행렬의 모든 값은 INF로 초기화 한다.

- 대각선 값 (i = j) 0으로 넣어준다.

- Edge 값을 입력한다.

 

2. K I J ! 3중 반복문을 통한 가중치 완화

 

https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

import kotlin.math.min

const val INF = 1_000_000_000

// n = 노드개수, m = 간선개수
var n = 0
var m = 0

lateinit var distance: Array<Array<Int>>
fun main() = with(System.`in`.bufferedReader()) {

    n = readLine().toInt()
    m = readLine().toInt()
    distance = Array(n + 1) { Array(n + 1) { INF } }

    for (i in 1 until distance.size) {
        for (j in 1 until distance.size) {
            if (i == j) distance[i][j] = 0
        }
    }

    for (i in 1..m) {
        val edgeInfo = readLine().split(" ").map { it.toInt() }
        val u = edgeInfo[0]
        val v = edgeInfo[1]
        val w = edgeInfo[2]
        distance[u][v] = min(distance[u][v], w)
    }

    for (k in 1 until distance.size) {
        for (i in 1 until distance.size) {
            for (j in 1 until distance.size) {
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
            }
        }
    }

    for (i in 1 until distance.size) {
        for (j in 1 until distance.size) {
            if (distance[i][j] == INF)
                print("${0} ")
            else
                print("${distance[i][j]} ")
        }
        println()
    }
}