Floyd Warshall

Floyd Warshall

• 그래프에서 도착할 수 있는 모든 쌍에대한 최단거리를 구하는 알고리즘
• 그래프를 기준으로 이차원배열 생성
• Dynamic Programing기법을 이용해 각 쌍의 최단거리를 계산 및 업데이트

 

예제) 그래프 최소 왕복 길이 계산

초기 cost

INF	1	5
INF	INF	2
INF	1	INF

플로이드 와샬 알고리즘 후 cost

INF	1	3
INF	3	2
INF	1	3

 

func floydWarshall(inputs: [[Int]], node: Int) -> Int {
    let INF = 987654321
    var result = INF
    var cost = Array(repeating: Array(repeating: INF, count: node), count: node)
    
    for input in inputs {
        cost[input[0] - 1][input[1] - 1] = input[2]
    }
    
    for k in (0..<node) {
        for i in (0..<node) {
            for j in (0..<node) {
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
            }
        }
    }
    
    for i in (0..<node) {
        result = min(result, cost[i][i])
    }
    
    return result
}

print(floydWarshall(inputs: [[1, 2, 1], [3, 2, 1], [1, 3, 5], [2, 3, 2]], node: 3)) // 3