[알고리즘] 최단 경로 구하기 - 3. 플로이드-워셜 알고리즘

|  플로이드-워셜 알고리즘

- 모든 노드의 최단 경로를 구하는 알고리즘으로 전체 간선을 인접 행렬로 표현하고 dp를 통해 최단 경로를 구하는 방식

핵심 : 전체 경로의 최단 경로 = 부분 경로의 최단 경로의 조합

- 기능 : 모든 노드 간에 최단 경로 탐색

- 특징 : 음수 가중치 Ok, 동적 계획법의 원리를 사용

- 시간복잡도 : O(V3)

 

|  플로이드-워셜 구현하기

1	배열을 선언하고 초기화
2	노드의 각 인접 노드 경로 입력
3	점화식으로 배열 업데이트
4	음수사이클 확인

 

[1] 배열을 선언하고 초기화

- 각각의 노드를 Start지점으로 두고 모든 Start지점에 대한 최단 거리를 구할 예정

	1	2	3	4	5
1	0	∞	∞	∞	∞
2	∞	0	∞	∞	∞
3	∞	∞	0	∞	∞
4	∞	∞	∞	0	∞
5	∞	∞	∞	∞	0

static int[][] distDP; // 행 : 출발점, 열 : 도착점
static final int INF = 100_000_000; // overflow방지 큰 값 지정

public static void floydWarshall(int V, int E, int[][] data, int start) {

    // 1. 배열을 선언하고 초기화
    distDP = new int[V + 1][V + 1];
    for (int i = 1; i < V + 1; i++) {
        for (int j = 1; j < V + 1; j++) {
            if (i != j) {
                distDP[i][j] = INF;
            }
        }
    }
        
}

 

[2] 노드의 각 인접 노드 경로 입력

- 먼저 dp에 인접 행렬를 입력하는 것

- 인접 행렬을 기준으로 각각의 경유지에 대한 최단 거리를 업데이트할 예정

// 2. 노드의 각 인접 노드 경로 입력
for (int i = 0; i < E; i++) {
    distDP[data[i][0]][data[i][1]] = data[i][2];
}

 

[3] 점화식으로 배열 업데이트

- 각각의 경유지에 관해서, 어떤 출발지~경유지 + 경유지~어떤 도착지가 최소일 경우를 구한다.

for 경유지 K에 관해
   for 출발지 S에 관해
    	for 도착지 E에 관해
          D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]);

// 3. 점화식으로 배열 업데이트
// :  어떤 경유지를 거쳐 가는 것이 가장 빠른 가를 파악
for (int k = 1; k < V + 1; k++) { // 경유지
     for (int s = 1; s < V + 1; s++) { // 출발지
        for (int e = 1; e < V + 1; e++) { // 도착지
            // 경유지를 출발지 또는 도착지로 두는 거리가 입력된 바 없으면 무시
            if (distDP[s][k] != INF && distDP[k][e] != INF) {
                distDP[s][e] = Math.min(distDP[s][e], distDP[s][k] + distDP[k][e]);
            }
        }
    }
}

 

[4] 음수 사이클의 경우

- 음수사이클의 경우, 위 알고리즘에서 자기자신의 dp지점이 음수로 나타나게 된다.

 

** 최종 코드

static int[][] distDP; // 행 : 출발점, 열 : 도착점
static final int INF = 100_000_000; // overflow방지 큰 값 지정

public static void floydWarshall(int V, int E, int[][] data, int start) {

    // 1. 배열을 선언하고 초기화
    distDP = new int[V + 1][V + 1];
    for (int i = 1; i < V + 1; i++) {
        for (int j = 1; j < V + 1; j++) {
            if (i != j) {
                distDP[i][j] = INF;
            }
        }
    }

    // 2. 노드의 각 인접 노드 경로 입력
    for (int i = 0; i < E; i++) {
        distDP[data[i][0]][data[i][1]] = data[i][2];
    }

    // 3. 점화식으로 배열 업데이트
    // :  어떤 경유지를 거쳐 가는 것이 가장 빠른 가를 파악
    for (int k = 1; k < V + 1; k++) { // 경유지
         for (int s = 1; s < V + 1; s++) { // 출발지
            for (int e = 1; e < V + 1; e++) { // 도착지
                // 경유지를 출발지 또는 도착지로 두는 거리가 입력된 바 없으면 무시
                if (distDP[s][k] != INF && distDP[k][e] != INF) {
                    distDP[s][e] = Math.min(distDP[s][e], distDP[s][k] + distDP[k][e]);
                }
            }
        }
    }

    // 출력
    for (int i = 1; i < V + 1; i++) {
        for (int j = 1; j < V + 1; j++) {
            if (distDP[i][j] >= INF) {
                System.out.printf("%5s ", "INF");
            } else {
                System.out.printf("%5d ", distDP[i][j]);
            }
        }
        System.out.println();
    }

}

 

 

[ 참고 및 출처 ]

부트캠프

Do it 알고리즘 코딩 테스트