📗[CS/Algorithm] 최단 경로 알고리즘 / 플로이드 워셜

• 플로이드 워셜 알고리즘 정의
  • 음수 사이클이 없는 그래프 내의 각 모든 정점에서 각 모든 정점까지의 최단거리를 구할 수 있는 알고리즘
    • 음수 사이클만 아니면, 음수 가중치를 갖는 간선이 존재해도 상관 x

• 사용법
  
  1. 인접 행렬 그래프 생성 ⇒ 초기화
     • 0개의 간선을 거쳐 모든 노드로 가는 방법
       • 자기 자신으로 갈 때 → 0
       • 그 외 다른 노드로 갈 수 있는 방법이 없으므로, 무한대 INF 값으로 초기화
     • 1개의 간선을 거쳐 모든 노드로 가는 경우 = 주어진 그래프에서 직접 연결된 경우를 생각
       • 해당 간선의 가중치로 초기화
         • 이때, 노드간 간선이 여러개 존재한다면 가장 작은 가중치 선택
  2. 위 방식으로 0개 ~ N개의 간선을 거친 경우의 최소 거리 비용을 비교하여, 인접행렬을 갱신해나간다.
     • 3개의 중첩 루프를 사용해 각 정점 쌍에 대한 최단 경로 갱신
     • 이때, i에서 j로 가는 경로와 i에서 k를 거쳐 j로 가는 경로를 비교해 더 짧은 경로를 선택

import java.io.*;
import java.util.*;

public class Main {
    static final int INF = 1_000_000_010;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 맵 크기 N*N
        int N = Integer.parseInt(br.readLine());
        // 간선 개수 M
        int M = Integer.parseInt(br.readLine());

        // 인접행렬 초기화
        // 간선 0개로 갈 수 있는 비용으로 초기화
        int[][] dist = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 자기 자신으로 가는 경우 -> 최소 비용 0
                if (i == j){
                    dist[i][j] = 0;
                    continue;
                }

                //그 외에는 무한대 값으로 초기화
                dist[i][j] = INF;
            }
        }

        // 주어진 입력에 따라 현재 그래프에서 간선 1개로 갈 수 있는 비용으로 초기화
        int a, b, c;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            // 정점간 간선 중 가장 최소 비용을 저장
            dist[a][b] = Math.min(dist[a][b], c);
            dist[b][a] = Math.min(dist[b][a], c);
        }

        // 플로이드 워셜 알고리즘 -> 3중 for문으로 구현
        for (int k = 0; k < N; k++) {

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 노드 i에서 j로 이동하는 경우와
                    // i에서 k를 거쳐 j로 가는 경로와 비교하여
                    // 더 작은 비용을 갱신
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (dist[i][j] == INF) {
                    System.out.print("INF");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}

• 시간 복잡도
  • 정점의 수가 V라면, O(V^3)