[Data Structure / Algorithms] Floyd-Warshall Algorithm

전성훈·2023년 11월 15일

Algorithms swift

Data Structure-Algorithm

목록 보기

29/35

주제: 모든 쌍 최단거리 찾기

플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘입니다.
이 알고리즘의 기본 아이디어는 각 노드 쌍에 대해 최단 경로를 찾는 것이며, 이를 위해 동적 프로그래밍 기법을 사용합니다.
이는 노드의 개수가 N이라고 할 때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문입니다.
다익스트라 알고리즘에서는 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 이용했습니다. 반면에 플로이드 워셜 알고리즘은 다익스트라 알고리즘과 다르게 2차원 리스트에 '최단 거리' 정보를 저장한다는 특징이 있습니다.
모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문입니다.

동작 방식

각 단계에서는 해당 노드를 거쳐 가는 경우를 고려합니다. 예를 들어 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면 됩니다. A -> 1번 노드 -> B로 가능 비용을 확인한 뒤에 최단 거리를 갱신합니다. 다시 말해 $_{N-1}P_2$ 개의 쌍을 단계마다 반복해서 확인하면 됩니다. 이때 $O(_{N-1}P_2)$ 는 $O(N^2)$ 이라고 볼 수 있기 때문에, 전체 시간 복잡도는 $O(N^3)$ 이라고 할 수 있습니다.
구체적인 점화식은 아래와 같습니다.

$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$
A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비고하여 더 작은 값으로 갱신하겠다는 것 입니다. 즉, 바로 이동하는 거리가 특정한 노드를 거쳐서 이동하는 거리 보다 더 많은 비용을 가진다면 이를 더 짧은 것으로 갱신합니다.

초기화
- 그래프의 모든 쌍 간의 거리를 나타내는 2차원 배열을 초기화합니다. 이 배열에서 배열 [i][j]는 노드 i에서 노드 j로 가는 최단 경로의 길이를 나타냅니다. 자기 자신으로의 경로는 0으로 설정하고, 직접 연결되지 않은 노드 쌍의 거리는 무한대로 설정합니다.
경로 갱신
- 알고리즘은 모든 노드 쌍에 대해 모든 노드를 중간 노드로 고려하여 최단 경로를 갱신합니다. 이 과정에서 [i][k] + [k][j] < [i][j] 이면 [i][j]를 새로운 경로 길이로 갱신합니다.
반복
- 위의 경로 갱신 과정을 모든 노드에 대해 반복합니다. 이 과정을 통해 모든 노드 쌍에 대한 최단 경로가 계산됩니다.

효율성

시간 복잡도: $O(N^3)$ , 여기서 N은 노드의 수 입니다. 모든 노드 쌍에 대해 모든 노드를 중간 노드로 고려해야 하기 때문입니다.
공간 복잡도: $O(N^2)$ , 알고리즘은 노드 간의 최단 경로 정보를 저장하기 위해 2차원 배열을 사용합니다.

한계

큰 그래프에서는 시간 복잡도가 O(N³)이므로 매우 비효율적일 수 있습니다.
이 알고리즘은 음수 사이클이 존재할 경우 제대로 작동하지 않습니다.

활용

데이터 네트워크 라우팅에서 최적의 경로를 찾는 데 사용될 수 있습니다.
사람들 간의 관계를 나타내는 그래프에서 가장 짧은 연결 경로를 찾는 데 사용됩니다.
맵 내에서의 최단 경로를 찾기에 사용됩니다.

구현

import Foundation

let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }

let N = testCase[0]
let M = testCase[1]

// Int.max로 하면 arithmetic overflow 발생한다. 
let INF = 10001

var graph = [[Int]](repeating: [Int](repeating: INF, count: N), count: N)

// 자기 자신으로 가는 비용 0으로 초기화
for i in 0..<N {
    for j in 0..<N {
        if i == j {
            graph[i][j] = 0
        }
    }
}

// 최초 2차원 리스트의 값은 무한으로 초기화하며, 각 간선에 대한 값으로 초기화 한다.
for _ in 0..<M {
    let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }
    graph[testCase[0] - 1][testCase[1] - 1] = testCase[2]
}

for k in 0..<N {
    for i in 0..<N {
        for j in 0..<N {
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        }
    }
}

// 또는 Int.max를 사용할 경우 INF보다 작을때만 작동할수있도록 설정하면 된다.
for k in 0..<N {
    for i in 0..<N {
        for j in 0..<N {
            if graph[i][k] < INF && graph[k][j] < INF {
                let newDistance = graph[i][k] + graph[k][j]
                if newDistance < graph[i][j] {
                    graph[i][j] = newDistance
                }
            }
        }
    }
}

예시 1. 미래 도시 (이것이 코팅 테스트이다.)

모든 도시는 양방향으로 연결되어있다. 또한 시작 위치는 1번이며, K번을 거치고 X로 가는 최단 거리를 구하고자한다.
이때 플루이드 워셜 알고리즘을 활용해서 모든 노드에서 최단거리를 구한다음, [1][k]와 [k][x]의 값을 더해주면 된다.

import Foundation

let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }

let N = testCase[0]
let M = testCase[1]

// Int.max로 하면 arithmetic overflow 발생한다.
let INF = 10001

var graph = [[Int]](repeating: [Int](repeating: INF, count: N), count: N)

// 자기 자신으로 가는 비용 0으로 초기화
for i in 0..<N {
    for j in 0..<N {
        if i == j {
            graph[i][j] = 0
        }
    }
}

// 최초 2차원 리스트의 값은 무한으로 초기화하며, 각 간선에 대한 값으로 초기화 한다.
for _ in 0..<M {
    let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }
    graph[testCase[0] - 1][testCase[1] - 1] = 1
    graph[testCase[1] - 1][testCase[0] - 1] = 1
}


let XandK = readLine()!.components(separatedBy: " ").map { Int($0)! }

for k in 0..<N {
    for i in 0..<N {
        for j in 0..<N {
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        }
    }
}

let result = graph[0][XandK[1] - 1] + graph[XandK[1] - 1][XandK[0] - 1]

if result >= INF {
    print(-1)
} else {
    print(result)
}

예시 2. 플로이드 (백준 골드 4)

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.
모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.
시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

예제 입력 1

예제 출력 1

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0

풀이

해당 조건에 맞춰서 그래프를 만든다음에 해당 그래프를 플루이드 워셜 알고리즘을 활용해서 변경한 후 그래프를 출력하면 된다.
여기서 위 문제에 조건이라하면, 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 이다. 즉, 최소 값을 구해야하는데, 해당 값이 최초 최소값보다 큰 값이 들어갈 수 있다는 말이다.
그렇기 때문에 graph의 값을 초기화 할때 기존 값보다 작은 값만 넣을 수 있다는 조건 처리를 추가해주면 된다.

import Foundation

// 도시의 개수
let N = Int(readLine()!)!
// 버스의 개수
let M = Int(readLine()!)!

// Int.max로 하면 arithmetic overflow 발생한다.
let INF = Int.max

var graph = [[Int]](repeating: [Int](repeating: INF, count: N), count: N)

// 자기 자신으로 가는 비용 0으로 초기화
for i in 0..<N {
    for j in 0..<N {
        if i == j {
            graph[i][j] = 0
        }
    }
}

// 최초 2차원 리스트의 값은 무한으로 초기화하며, 각 간선에 대한 값으로 초기화 한다.
for _ in 0..<M {
    let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }
    let to = testCase[0] - 1
    let destination = testCase[1] - 1
    let weight = testCase[2]
    
    if graph[to][destination] > weight {
          graph[to][destination] = weight
      }
}

for k in 0..<N {
    for i in 0..<N {
        for j in 0..<N {
        // INF를 Int.max로 해줘서 해당 조건문 생성 [i][k], [k][j] 둘 다 INF보다 작아야함
        // 즉, 둘 중 하나라도 INF 값이면 무시 
            if graph[i][k] < INF && graph[k][j] < INF {
                let newDistance = graph[i][k] + graph[k][j]
                if newDistance < graph[i][j] {
                    graph[i][j] = newDistance
                }
            }
        }
    }
}

for i in 0..<N {
    for j in 0..<N {
        if graph[i][j] == INF {
            graph[i][j] = 0
        }
        
        print(graph[i][j],terminator: " ")
    }
    
    print()
}

예시 3. 역사 (백준 골드 3)

문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.
세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

예제 입력 1

예제 출력 1

0
-1
1

풀이

해당 문제는 단방향 그래프, 최단 거리 문제이다.
사건의 전후 관계를 찾을때는 전체 모든 최단거리를 구할 수 있는 플로이드 워셜 알고리즘이 적절하다.
왜냐하면 주어진 전후관계에 대해 다음에 일어난 사건에 1의 가중치를 부여하고, 플로이드 워셜 알고리즘을 활용해서 모든 최단거리에 대해 가중치 값을 최신화 해주면 된다.
최신화된 가중치 그래프를 통해 주어진 테스트케이스에서 앞이 더 높으면 -1, 뒤가 더 높으면 1 이렇게 부여해주면 해결할 수 있다.

import Foundation

let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }

// 사건의 개수
let N = testCase[0]
// 전후 관계의 개수
let K = testCase[1]

let INF = 100000

// 최초 무제한 값으로 초기화 
var graph = [[Int]](repeating: [Int](repeating: INF, count: N), count: N)

// 자기 자신으로 가는 비용 0으로 초기화
for i in 0..<N {
    for j in 0..<N {
        if i == j {
            graph[i][j] = 0
        }
    }
}

// 최초 2차원 리스트의 값은 무한으로 초기화하며, Edge가 있는 각 간선에 대해 1로 초기화
for _ in 0..<K {
    let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }
    let to = testCase[0] - 1
    let destination = testCase[1] - 1
    let weight = 1
    
    graph[to][destination] = weight
}

for k in 0..<N {
    for i in 0..<N {
        for j in 0..<N {
            if graph[i][k] < INF && graph[k][j] < INF {
                let newDistance = graph[i][k] + graph[k][j]
                if newDistance < graph[i][j] {
                    graph[i][j] = newDistance
                }
            }
        }
    }
}

// 유추가 불가능할 때는 0을 나타내기 위해 INF을 '0'으로 초기화 
for i in 0..<N {
    for j in 0..<N {
        if graph[i][j] == INF {
            graph[i][j] = 0
        }
    }
}


let testResult = Int(readLine()!)!

for _ in 0..<testResult {
    let testCase = readLine()!.components(separatedBy: " ").map { Int($0)! }
    
    let i = testCase[0] - 1
    let j = testCase[1] - 1
    
    if graph[i][j] > graph[j][i] {
        print("-1")
    } else if graph[i][j] < graph[j][i] {
        print("1")
    } else {
        print("0")
    }
}

출처(참고문헌)

이것이 코딩 테스트이다 - 나동빈

제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.

감사합니다.

전성훈

이전 포스트

[Data Structure / Algorithms] Dijkstra's Algorithm

다음 포스트

[Data Structure / Algorithms] Floyd-Warshall Algorithm

Data Structure-Algorithm

주제: 모든 쌍 최단거리 찾기

플로이드 워셜 알고리즘

동작 방식

효율성

한계

활용

구현

예시 1. 미래 도시 (이것이 코팅 테스트이다.)

예시 2. 플로이드 (백준 골드 4)

문제

입력

출력

예제 입력 1

예제 출력 1

풀이

예시 3. 역사 (백준 골드 3)

문제

입력

출력

예제 입력 1

예제 출력 1

풀이

출처(참고문헌)

[Data Structure / Algorithms] Dijkstra's Algorithm

[Data Structure / Algorithms] Disjoint-Set Structure (Union - Find Algorithms)

0개의 댓글