Floyd-Warshall

음수 사이클이 없는 그래프 내의 각 모든 정점에서 각 모든 정점까지의 최단거리를 모두 구하는 알고리즘.

vs 다익스트라

다익스트라는 그래프에 음수 간선 자체가 존재할 수 없지만, 플로이드 워셜은 음수 사이클만 존재하지 않으면, 음의 가중치를 갖는 간선이 존재해도 상관 없음.

Folyd-Warshall 알고리즘 접근

다이나믹 프로그래밍 기법을 사용 + 인접 행렬을 이용하여 각 노드간 최소 비용을 계산함.
모든 노드에서, 모든 노드로 가는 최소 비용을 단계적으로 갱신*하면서 진행되는 알고리즘임.

모든 노드에 대해서 똑같이 고려해주는 것이 중요함.
예를 들어서 start 노드에서 end 노드까지 향해야 할 때, 몇 개의 간선, 몇 개의 노드를 거쳐서 가는 경우까지 차례로 모두 고려해야 한다는 의미.

---

*노드에서 노드로 가능 간선의 개수가 0개에서 N개까지의 몇 개의 간선을 거쳐서 해당 노드로 가는지를 모두 고려함.

+) 참고로 경유하는 노드의 수는 1개부터 시작하는데, 예를 들어서 1번 노드에서 2번 노드를 연결하는 간선이 있다고 할때,
1번 노드에서 2번 노드로 바로 간선을 타고 이동하는 것이 아닌 1번 노드에서 2번 노드를 경유하여 2번 노드로 이동하는 것이라고 이해해야 함.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[][] dist = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                    continue;
                }
				// Integer.MAX_VALUE로 설정하면 + 계산으로 인해 음수 범위로 넘어가 버림.
                dist[i][j] = 100_000_000;
            }
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            dist[a][b] = Math.min(dist[a][b], c);
            dist[b][a] = Math.min(dist[b][a], c);
        }

        for (int i = 0; i < n; i++) { // 경유하는 노드 수 (경유 노드는 1부터 시작함)
            for (int j = 0; j < n; j++) { // 노드 j에서 k로 가능 경우
                for (int k = 0; k < n; k++) {
					// k번째 노드를 거쳐가는 비용이 기존 비용보다 더 작은 경우 갱신
					// 또는 연결이 안되어있던 경우(Integer.MAX_VALUE), 연결 비용 갱신
                    dist[j][k] = Math.min(dist[j][k], dist[j][i] + dist[i][k]);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
				// 연결이 안된 경우
                if (dist[i][j] == Integer.MAX_VALUE) bw.write("INF ");
                else bw.write(dist[i][j] + " ");
            }
            bw.write("\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

참고 자료

https://sskl660.tistory.com/61