플로이드-워셜 알고리즘

 

  • 모든 정점 쌍 간 최단 경로를 찾는 알고리즘

  • 3개의 중첩 for문을 사용하는 매우 단순한 알고리즘!

  • 그래프의 두 정점 사이의 직접 연결된 경로가 있거나, 다른 정점 k를 경유하는 경로가 있을 경우, 둘 중 더 짧은 경로를 선택하는 방식

  • 시간복잡도 : O(N^3)

 

 

 

동작 원리

1.  인접 행렬을 기반으로 모든 정점 간 최단 거리를 초기화. 인접하지 않은 경우는 무한대로 설정

 

2. 각 정점을 중간 노드로 설정해 두 정점 간 경로 갱신

 

3. 최종적으로 가장 짧은 경로를 도출

 

 

 

 

장점

  • 메모리를 비교적 덜 차지함

  • 음수 가중치가 있어도 적용할 수 있음

  • 간단하고 직관적임

 

 

 

단점

  • 시간복잡도가 급격히 증가하므로, 정점 수가 적을 때만 적용할 수 있음.

  • 음수 사이클이 존재하는 경우엔 적용 불가

 

 

구현

 

import java.util.Arrays;

public class FloydWarshall {

    // 무한대를 나타내는 상수
    static final int INF = Integer.MAX_VALUE;
    
    // 플로이드-워셜 알고리즘을 실행하는 메서드
    public static void floydWarshall(int[][] graph) {
        int V = graph.length;
        // 최단 거리를 저장할 배열 생성
        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];
            }
        }
		
        // 각 정점 k를 중간 정점으로 사용하여 경로를 최적화
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    // i에서 j로 가는 경로가 k를 거쳐 더 짧으면 업데이트
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
            // 단계별로 배열 상태 출력
            System.out.println("경유 정점 " + k + "을(를) 거친 후 거리 배열:");
            printSolution(dist);
        }

        // 최종 결과 출력
        printSolution(dist);
    }

    // 최단 경로 배열을 출력하는 메서드
    public static void printSolution(int[][] dist) {
        int V = dist.length;
        System.out.println("정점 쌍 간의 최단 거리:");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == INF)
                    System.out.print("INF ");
                else
                    System.out.print(dist[i][j] + "   ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 그래프의 인접 행렬 표현 (0은 자기 자신으로 가는 경로)
        int[][] graph = { 
            { 0, 5, INF, 10 }, 
            { INF, 0, 3, INF }, 
            { INF, INF, 0, 1 }, 
            { INF, INF, INF, 0 }
        };

        // 플로이드-워셜 알고리즘 실행
        floydWarshall(graph);
    }
}