[알고리즘] 최단 경로 알고리즘: Floyd-Warshall

📌 플로이드 워셜 알고리즘

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산합니다.

• 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행합니다.
  하지만, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않습니다.
  

• 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장합니다.

• 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속합니다.

• 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인합니다.
  a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사합니다.

💡 동작 과정

• [초기 상태] 그래프를 준비하고 최단 거리 테이블을 초기화한다
  

• [Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다
  

• [Step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다
  

• [Step 3] 3번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다
  

• [Step 4] 4번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다
  

✨ 알고리즘 구현 (Java)

import java.util.*;

public class Main {

    public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
    // 노드의 개수(N), 간선의 개수(M)
    // 노드의 개수는 최대 500개라고 가정
    public static int n, m;
    // 2차원 배열(그래프 표현)를 만들기
    public static int[][] graph = new int[501][501];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        // 최단 거리 테이블을 모두 무한으로 초기화
        for (int i = 0; i < 501; i++) {
            Arrays.fill(graph[i], INF);
        }

        // 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                if (a == b) graph[a][b] = 0;
            }
        }

        // 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
        for (int i = 0; i < m; i++) {
            // A에서 B로 가는 비용은 C라고 설정
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph[a][b] = c;
        }

        // 점화식에 따라 플로이드 워셜 알고리즘을 수행
        for (int k = 1; k <= n; k++) {
            for (int a = 1; a <= n; a++) {
                for (int b = 1; b <= n; b++) {
                    graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
                }
            }
        }

        // 수행된 결과를 출력
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
                if (graph[a][b] == INF) {
                    System.out.print("INFINITY ");
                }
                // 도달할 수 있는 경우 거리를 출력
                else {
                    System.out.print(graph[a][b] + " ");
                }
            }
            System.out.println();
        }
    }
}

다익스트라 VS 플로이드-워샬

특징	다익스트라 알고리즘	플로이드-와샬 알고리즘
목적	단일 출발점 최단 경로 구하기	모든 정점 쌍의 최단 경로 구하기
시간 복잡도	O((V + E) log V)	O(V^3)
사용 조건	양수 가중치만 가능	음수 간선 허용, 음수 사이클 불가능
적합한 그래프	희소 그래프 (정점이 많고 간선이 적은 경우)	작은 그래프 (정점 수가 적을 때)
음수 가중치	지원하지 않음	지원 가능, 음수 사이클은 허용하지 않음
공간 복잡도	O(V)	O(V^2)

1. 알고리즘의 목적

• 다익스트라 알고리즘

  • 특정 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다.
  • 단일 시작점 최단 경로 문제에 적합합니다.
  • 예: 한 도시에서 다른 도시들로 가는 최단 경로를 구하고 싶을 때.

• 플로이드-와샬 알고리즘

  • 모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘입니다.
  • 모든 시작점에서 모든 끝점까지의 최단 경로를 한 번에 구할 수 있습니다.
  • 예: 모든 도시들 사이의 최단 경로를 구하고 싶을 때.

2. 알고리즘의 구현 방식

• 다익스트라 알고리즘

  • 우선순위 큐(힙)를 사용하여 출발점에서 가장 가까운 정점부터 차례대로 확장해 나가면서 최단 경로를 계산합니다.
  • 출발점으로부터의 최단 경로만 업데이트합니다.

• 플로이드-와샬 알고리즘

  • 동적 계획법(DP)을 사용하여 경유하는 모든 정점에 대해 모든 경로를 계속해서 갱신해 나갑니다.
  • 3중 루프를 사용하여 모든 정점 쌍에 대해 최단 경로를 갱신합니다.

---

References

(이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘