Floyd-Warshall 알고리즘

개요

플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘으로, 동적 계획법(DP)을 활용하여 구현

특징

• 한 번 실행하면 모든 정점 간 최단 거리를 한꺼번에 구할 수 있음
• 시간 복잡도는 O(N³)로 모든 정점 쌍을 고려해야 하므로 다익스트라O(N²) 또는 O(E log N)보다 느림

구현

• 최적의 구현을 위해 2차원 배열을 사용
• 경로 갱신을 3중 for문으로 수행

원리

기본 개념

• dist[i][j] = 정점 i에서 j로 가는 최소 비용
• 초기 상태에서는 직접 연결된 경로만 사용하여 초기화하고, 나머지는 INF(무한대)로 설정
• 이후, 모든 정점을 “경유점”으로 사용하여 더 짧은 경로를 찾음

점화식 (DP 테이블 갱신)

• 어떤 두 정점 ( i, j )에 대해, 중간 정점 ( k )를 경유하는 경우의 최단 거리 갱신:

\[\text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][k] + \text{dist}[k][j])\]

• 즉, 기존의 i → j 경로보다 i → k → j 경로가 더 짧다면 갱신하는 방식

세 개의 반복문을 사용하여 점화식을 적용

• 바깥쪽 루프 (k) → 경유점으로 사용할 정점
• 두 번째 루프 (i) → 출발 정점
• 세 번째 루프 (j) → 도착 정점

모든 정점 쌍에 대해 최단 거리 계산 완료

• 한 번의 실행으로 모든 최단 경로를 구할 수 있음

예시

코드

FloydWarshall

void FloydWarshall(vector<vector<int>>& dist, int n) {
    for (int k = 0; k < n; k++) {         // 경유점
        for (int i = 0; i < n; i++) {     // 출발점
            for (int j = 0; j < n; j++) { // 도착점
                if (dist[i][k] != INF && dist[k][j] != INF) {  
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

main()

int main() {
    int n = 4;  // 정점 개수
    vector<vector<int>> dist = {
        {0, 3, INF, 7}, {8, 0, 2, INF}, {5, INF, 0, 1}, {2, INF, INF, 0}};

    FloydWarshall(dist, n);

    // 결과 출력
    cout << "Result matrix:" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF)
                cout << "INF ";
            else
                cout << dist[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

실행 결과

Result matrix:
0 3 5 6
5 0 2 3
3 6 0 1
2 5 7 0

수행 과정

1. 초기 거리 행렬 설정

정점	A	B	C	D
A	0	3	∞	7
B	8	0	2	∞
C	5	∞	0	1
D	2	∞	∞	0

초기에는 직접 연결된 거리만 표기되고, 연결되지 않은 곳은 ∞(INF)로 설정됨

---

2. 정점 A를 경유지(k=0)로 사용

\[\text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][A] + \text{dist}[A][j])\]

정점	A	B	C	D
A	0	3	∞	7
B	8	0	2	15
C	5	∞	0	1
D	2	5	∞	0

D → B 경로가 갱신됨: D → A → B (기존 INF → 2+3 = 5)
B → D 경로 갱신됨: B → A → D (기존 INF → 8+7 = 15)

---

3. 정점 B를 경유지(k=1)로 사용

\[\text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][B] + \text{dist}[B][j])\]

정점	A	B	C	D
A	0	3	5	7
B	8	0	2	4
C	5	∞	0	1
D	2	5	∞	0

A → C 경로 갱신됨: A → B → C (기존 INF → 3+2 = 5)
B → D 경로 갱신됨: B → C → D (기존 15 → 2+1 = 4)

---

4. 정점 C를 경유지(k=2)로 사용

\[\text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][C] + \text{dist}[C][j])\]

정점	A	B	C	D
A	0	3	5	6
B	8	0	2	3
C	5	∞	0	1
D	2	5	7	0

A → D 경로 갱신됨: A → C → D (기존 7 → 5+1 = 6)
B → D 경로 갱신됨: B → C → D (기존 4 → 2+1 = 3)

---

5. 정점 D를 경유지(k=3)로 사용

최종 최단 거리 행렬:

정점	A	B	C	D
A	0	3	5	6
B	5	0	2	3
C	3	6	0	1
D	2	5	7	0

---

그래프

초기

graph TD;
    A((A)) -->|3| B((B));
    A -->|7| D((D));
    B -->|2| C((C));
    C -->|1| D;
    D -->|2| A;
    C -->|5| A;
    B -->|8| A;

연산 결과

graph TD;
    A((A)) -->|3| B((B));
    A -->|6| C((C));
    A -->|7| D((D));
    B -->|2| C;
    B -->|3| D;
    C -->|1| D;
    C -->|5| A;
    D -->|2| A;