플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 처음 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 

시간 복잡도는 3중 반복문으로 O(n^3)이다. 

 

코드는 다음과 같다. 이외로 간단하다.

for(int k = 0; k < N; ++k)
{
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j}
        {
            if(d[i][j] > d[i][k] + d[k][j]) 
                d[i][j] = d[i][k] + d[k][j];
        }
    }
}

선행 조건으로 배열에는 두 정점 간의 비용이 초기화되어 있어야 한다. 두 정점 간의 연결이 없는 경우 무한대로 초기화한다.

 

무한대로 초기화 하는 이유는 이 무한대 값을 이용해 두 정점 간의 연결 여부를 파악하기 위해서다. 무한대가 아니라면 두 정점이 연결되어 있다는 뜻이다.

 

무한대를 넣는 이유는 위 코드의 조건문을 보면 알 수 있다. 꼭 무한대가 아니더라도 문제의 최댓값이 존재한다면 그 값을 넣어도 무관하다.

for(int i = 1; i <= n; ++i)
{
    for(int j = 1; j <= n; ++j)
    {
        d[i][j] = (i == j) ? 0 : ∞(문제의 최대값);
    }
}

d 배열에 주어진 정점 간의 비용을 넣어준다. 그 후 그래프 구현을 위한 인접 배열을 만든다.

for(int i = 1; i <= m; ++i)
{
    int v1 = 정점1;
    int v2 = 정점2;
    int cost = 비용;
    
    // 단방향
    d[a][b] = cost;
    
    // 양방향
    d[a][b] = cost;
    d[b][a] = cost;
}

 

플로이드 알고리즘의 각각 반복문의 역할을 알아보자.

 

첫번째 반복문 => 거쳐가는 정점

두 번째 반복문 => 출발하는 정점

세 번째 반복문 => 도작하는 정점

 

세 번째 반복문의 조건문만 이해하면 알고리즘을 이해할 수 있다.

if(d[i][j] > d[i][k] + d[k][j]) 
    d[i][j] = d[i][k] + d[k][j];

k = 거쳐가는 정점, i = 출발 정점, j = 도착 정점이었다. 예를 들어 1 -> 4 최단 경로를 살펴본다고 하자.

d[1][4] = d[1][k] + d[k][4]
              (1, 1) +   (1, 4) (점 자기자신을 가는 길은 존재하지 않으므로 X)
              (1, 2) +   (2, 4) => 1 -> 2 + 2 -> 4
              (1, 3) +   (3, 4) => 1 -> 3 + 3 -> 4
              (1, 4) +   (4, 4) (X)

만약 K의 값이 4라면, d[1][4]는 총 4번의 루프를 돈다. 루프를 돌 때마다 거쳐가는 정점(K)이 바뀌면서 갱신된다. 

 

K가 2일 경우 1 -> 2의 경로 2 -> 4의 경로 비용을 더한 결과가 나오는데 이것이 기존의 값보다 작을 경우 그것은 비용이 더 적은 것이므로 갱신해준다. (갱신되었다는 뜻은 '경유지를 거쳐서 두 정점이 연결' 혹은 '경유지를 거치지 않고 연결된 거리'가 최단 경로라는 뜻이다.)

 

k가 3일 경우 위처럼 1 -> 3의 경로 3 -> 4의 경로 비용을 더한 결과가 나오고 역시 이전 값보다 더 작으면 갱신해준다. 

 

이렇게 모든 경로를 확인함으로써, d 배열에는 정점 간의 최단 경로만 구해지게 된다. 위에서 제대로 초기화해줬기 때문에 같은 정점이나 연결되지 않은 경우는 신경 쓸 필요가 없다.

 

문제에 따라 알맞은 그래프 형식을 써야 한다는 주의점이 있다. 

 

---

내용에 대한 출처는 https://mygumi.tistory.com/110입니다.