Problem Solving/알고리즘

코딩테스트에서 자주 쓰는 C++ STL 라이브러리, 자료구조, 알고리즘 정리(3) - 플로이드 와샬(Floyd-Warshall)

돌돌김 2021. 1. 13. 03:55

Floyd-Warshall

 

Floyd-Warshall은 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 다 구하는 것이다.

또한, 음수 가중치의 경우도 구할 수 있다.

알고리즘은 비교적 간단하다.

 

  • 관련 문제

  • 기본 개념

    • 3중 for loop 사용

    • 방향, 무방향 그래프 둘다 사용가능, 사이클이 생기면 안된다

    • 음의 가중치 적용 가능

    • a->b로 가는 최단거리가 a->c->b보다 크면 그 값을 갱신한다

    • 아래의 조건문이 핵심이다

      if (arr[i][k] + arr[k][j] < arr[i][j]) { // k를 거쳐가는게 더 작으면
          arr[i][j] = arr[i][k] + arr[k][j]; // arr[i][j] 값 갱신
      }
  • 시간 복잡도

    • O(n^3)

floyd 구현

각 반복문의 위치가 중요하다.

  • 바깥 loop이 거쳐가는 노드
  • 두번째 loop는 출발하는 노드
  • 가장 안쪽 loop는 도착하는 노드

 

입력

        #define INF 987654321
        int main() {
            cin >> n >> m;
            for (int i = 0; i < m; i++) {
                cin >> from >> to >> cost;
                if (arr[from][to] != 0) { // 노드 A에서 노드 B로 직행하는 방법이 2개 이상인 경우
                    arr[from][to] = min(arr[from][to], cost); // 방향 그래프
                }
                else {
                    arr[from][to] = cost;
                }
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j)continue;
                    if (arr[i][j] == 0)
                        arr[i][j] = INF; // 갈 수 없는 곳은 무한대
                }
            }

floyd()

        void floyd() {
            for (int k = 1; k <= n; k++) {// k : 거쳐가는 노드
                for (int i = 1; i <= n; i++) { // i : from
                    for (int j = 1; j <= n; j++) { // j : to
                        if (arr[i][k] + arr[k][j] < arr[i][j]) { // k를 거쳐가는게 더 작으면
                            arr[i][j] = arr[i][k] + arr[k][j]; // 값 갱신
                        }
                    }
                }
            }
        }