Today I Learned

오늘은 저번에 정리했던 다익스트라 알고리즘과 같은 최단 경로 알고리즘인 플로이드 워셜 알고리즘에 대해 정리해보려 한다.

최단 경로 알고리즘 비교

이미지 출처 : https://loosie.tistory.com/m/146

• 다익스트라는 한 정점에서 다른 모든 정점의 최단 경로를,
  플로이드 워셜은 모든 정점에서 다른 모든 정점의 최단 경로를 구한다.

• 다익스트라는 매번 가장 적은 비용을 가진 노드를 하나씩 선택하는 로직이고,
  플로이드 워셜은 거쳐가는 정점을 기준으로 최단거리를 구하도록 하는 로직이다.

플로이드 워셜

그래프에서 가능한 모든 노드 쌍에 대해 최단 경로를 구하는 알고리즘

• DP를 기반으로 해서 중간 노드를 거쳐 가는 경우를 고려해 최단 경로를 구한다.

• 구현 시 3중 for문을 사용하므로 시간복잡도는 O(V^3)

• 시간복잡도가 높기때문에 정점의 개수가 많으면 다익스트라 같은 다른 알고리즘을 쓰는 것이 좋다. 하지만 정점의 개수가 적당하고 모든 정점간의 최단 경로를 구해야 하는 상황이면 효과적이다.

구현 과정

1. 초기 그래프 설정
   먼저 그래프의 초기 상태를 설정한다. 각 노드 간의 직접적인 연결 상태를 표현한 2차원 배열을 생성하고 초기화한다. 만약 두 노드 사이에 직접적인 연결이 없다면 무한대(혹은 가능한 최대값)로 설정한다.

2. 중간 노드 거쳐가는 경우 고려
   플로이드 워셜은 모든 노드를 중간 노드로 고려하여 최단 경로를 갱신하는 단계를 반복한다. 즉, 각 노드 쌍 (A, B)에 대해 A를 거쳐 B로 가는 경로를 검사하고 더 짧은 경로를 찾는다. 두 경로의 길이를 비교하고 더 작은 값으로 경로를 갱신한다.

3. 최단 경로 갱신
   위의 단계를 모든 노드와 중간 노드에 대해 반복한다. 2차원 배열은 계속 갱신되며, 모든 노드 간의 최단 경로 길이를 계산하게 된다.

코드 구현(Java)

public class A_FloydWarshall {
    // Integer.MAX_VALUE는 덧셈과정에서 overflow가 발생할 수있으므로 큰 값으로 초기화
    final static int INF = 999999, V = 4;

    void floydWarshall(int graph[][]) {
        int dist[][] = new int[V][V];

        // 초기값 설정
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // 플로이드 워셜 알고리즘 적용
        for (int m = 0; m < V; m++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][m] + dist[m][j] < dist[i][j])
                        dist[i][j] = dist[i][m] + dist[m][j];
                }
            }
        }

        printSolution(dist);
    }
    // 출력
    void printSolution(int dist[][]) {
        for (int i=0; i<V; ++i) {
            for (int j=0; j<V; ++j) {
                if (dist[i][j] == INF)
                    System.out.print("X   ");
                else
                    System.out.print(dist[i][j] + "   ");
            }
            System.out.println();
        }
    }

    public static void main (String[] args) {
        int graph[][] = { {0, 5, INF, 10},
                          {INF, 0, 3, INF},
                          {4, INF, 0, 1},
                          {2, 5, 8, 0} };
        A_FloydWarshall fw = new A_FloydWarshall();
        fw.floydWarshall(graph);
    }
}