What is Floyd-Warshall Algorism?

• 모든 쌍 최단 경로(All - Pairs Shortest Path)문제를 해결하기 위한 알고리즘으로, 주어진 가중치 그래프 내의 모든 정점 쌍 간의 최단 경로를 찾음. 여기서 가중치 그래프란 각 간선에 가중치(비용)이 할당된 그래프를 의미하며, 최단 경로란 주어진 두 정점 사이를 연결하는 경로 중 간선의 가중치 합이 최소인 경로를 말함

👉🏻 즉, 한번의 실행으로 모든 노드간 최단 경로를 구할 수 있는 것

위 그림과 같이 모든 노드간의 최단거리를 구해야하므로 2차원 배열로 나타낸다. 그리고 라운드의 수는 N개의 노드가 존재한다면, 라운드는 N라운드까지 존재하며, 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 값을 줄이는 과정을 반복한다.

초기 그래프를 2차원 배열로 나타내면 다음과 같다. 여기서 해당 노드에서 특정 노드까지 가는 길이 없다면 ∞로 표현한다.

Node(1) 기준

Node(1) → Node(1) = 0, Node(1) → Node(2) = 5, Node(1) → Node(3) = 없음(∞), Node(1) → Node(4) = 9, Node(1) → Node(5) = 1

Round 1 : 1번 Node를 새로운 중간 노드로 설정
(💡 Round N : N번 Node를 새로운 중간 노드로 설정)

위 그림에서 보면 알 수 있듯이 Node(1) ↔️ Node(3)은 현재 최단 경로로 가는 방법이 없고,
중간 노드(Node(1))가 자기 자신이기 때문에 ∞로 둔다.
Node(2) → Node(4)로 가는 최단 경로는 없으나, Node(1)을 중간 노드로 선정할 경우
Node(2) → Node(1) → Node(4) (길이 5 + 9 = 14)로 갈 수있다.
마찬가지로, Node(2) → Node(5) 역시 Node(2) → Node(1) → Node(5) (길이 5 + 1 = 6)로 갈 수 있다.
❗️ 각 노드는 대칭으로 존재하기때문에 대칭으로 존재하는 값도 같이 수정해준다.

Round 2 : 2번 Node를 새로운 중간 노드로 설정

Node(1) ↔️ Node(3)은 현재 최단 경로로 가는 방법은 없지만, 중간 노드(Node(2))로 선정할 경우 Node(1) → Node(2) → Node(3) (길이 5 + 2 = 7)로 갈 수 있다.
Node(3) ↔️ Node(5)은 현재 최단 경로로 가는 방법은 없지만, 중간 노드(Node(2))로 선정할 경우 Node(3) → Node(2) → Node(1) → Node(5) (길이 2 + 5 + 1 = 8)로 갈 수 있다.

Round 3 : 3번 Node를 새로운 중간 노드로 설정

Node(2) ↔️ Node(4)는 현재 가중치 14로 업데이트되어 있지만, 중간 노드(Node(3))로 선정할 경우 Node(2) → Node(3) → Node(4) (길이 2 + 7 = 9)로 현재 가중치 14보다 9가 작으므로 9로 업데이트 된다.

Round 4 : 4번 Node를 새로운 중간 노드로 설정

Node(3) ↔️ Node(5)은 현재 최단 경로로 가는 방법은 없지만, 중간 노드(Node(4))로 선정할 경우 Node(3) → Node(4) → Node(5) (길이 7 + 2 = 9)로 현재 가중치 8보다 크기 때문에 현재 가중치 8로 유지된다.

Round 5 : 5번 Node를 새로운 중간 노드로 설정`

Node(4) ↔️ Node(1)는 현재 최단 경로 가중치 9로, 중간 노드(Node(5))로 선정할 경우 Node(4) → Node(5) → Node(1) (길이 2 + 1 = 3)로 현재 가중치 9보다 작으므로 3으로 업데이트된다.
Node(4) ↔️ Node(2)는 현재 가중치 9로, 중간 노드(Node(5))로 선정할 경우 Node(4) → Node(5) → Node(1) → Node(2) (길이 2 + 1 + 5 = 8)로 현재 가중치 9보다 작으므로 8로 업데이트된다.

Round(N)까지 수행 결과 ∞값이 최단 경로의 값으로 바뀐것을 알 수 있다.

플로이드 와샬 알고리즘의 특징

• 시간 복잡도 : 플로이드 와샬 알고리즘의 시간 복잡도는 O(n^3)으로 n은 그래프의 정점 수.
• 음의 가중치를 가진 간선(비용, 거리)자체는 문제가 되지 않지만, 이러한 간선들이 사이클을 형성하여 그 총합이 음수가 되는 경우(음의 사이클 = 총합이 0보다 작을 때)는 존재하면 안됨.

package programmers;

public class FloydWarshall {
    public static final int INF = 10000000; // 경로가 없는 경우를 나타내는 값

    public static void floydWarshall(int n, int[][] connections) {
        int[][] graph = new int[n+1][n+1];

        // 그래프 초기화
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    graph[i][j] = 0;
                } else {
                    graph[i][j] = INF;
                }
            }
        }
        
        // 간선 데이터 입력
        for (int[] connection : connections) {
            int x = connection[0];
            int y = connection[1];
            int weight = connection[2];

            graph[x][y] = weight;
            graph[y][x] = weight; // 대칭되게 값을 넣기
        }

        // 플로이드-워셜 알고리즘 적용
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][k] != INF && graph[k][j] != INF) {
                        graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                    }
                }
            }
            for (int i = 1; i <= n; i++) {
            	for (int j = 1; j <= n; j++) {
            		if (graph[i][j] == INF) {
            			System.out.print("INF ");
            		} else {
            			System.out.print(graph[i][j] + " ");
            		}
            	}
            	System.out.println();
            }
            System.out.println();
        }
        
    }

    public static void main(String[] args) {
        int n = 5; // 노드의 수
        int[][] connections = {
            {1, 2, 5},
            {2, 3, 2},
            {3, 4, 7},
            {4, 1, 9},
            {4, 5, 2},
            {5, 1, 1}
        };

        floydWarshall(n, connections);
    }
}