https://www.acmicpc.net/problem/11404

플로이드

풀이

모든 노드 간 최단 거리를 구하는 문제이다.

그래프에서 노드 간 최단 거리를 구하는 알고리즘에는 대표적으로 다익스트라 알고리즘이 있다.

하지만 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이고 모든 간선의 비용의 값이 양수여야 한다.

하지만 문제에서는 모든 노드 간의 최단 거리를 구해야하고 음의 간선도 존재하기 때문에 다익스트라 알고리즘으로 풀 수 없다.

이 때 사용하는 알고리즘이 플로이드-와샬 알고리즘이다.

2차원 인접행렬로 나타내어진 그래프가 있을때, 각 사이클마다 중간 노드를 선택 해당 노드를 거쳤을 때 거리와 기존의 거리를 비교 더 짧은 것을 선택한다.

의사코드는 위와 같다. 총 3개의 for문이 있는데 첫 for문은 중간 노드를 선택하는 과정이고 아래 2개의 for문은 인접행렬을 탐색한다.

최단 거리를 갱신해야는데 갱신하는 과정도 의사코드에 나타난다.

dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]

점화식은 위와 같기 때문에 알고리즘 자체만 이해하면 구현은 간단하다.

코드

import java.io.*;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static final int INF = 100000001;

    public static void main(String[] args) throws IOException {
        // write your code here
        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[][] graph = new int[n + 1][n + 1];
        int[][] dist = new int[n + 1][n + 1];

        for(int i = 1;i<=n;i++) {
            for(int j = 1;j<=n;j++)
                graph[i][j] = INF;
        }

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);
            int c = Integer.parseInt(line[2]);
            graph[a][b] = Math.min(graph[a][b], c);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    dist[i][j] = 0;
                else {
                    dist[i][j] = graph[i][j];
                }
            }
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

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

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