플루이드-와샬 (파이썬, 자바)

플로이드-와샬 알고리즘은 그래프에서 모든 정점 간의 최단 거리를 구하는 알고리즘입니다. 간단하게 말하면, 모든 노드 쌍에 대해서 해당 노드 쌍을 연결하는 최단 경로를 찾는 알고리즘!

플로이드-와샬 알고리즘은 다음과 같은 과정으로 동작합니다:

1. 각 노드에서 자기 자신으로 가는 비용을 0으로, 그 외에는 무한대(inf 혹은 매우 큰 수)로 초기화합니다.
2. 주어진 간선 정보를 이용해 해당 두 노드 간의 비용을 갱신합니다.
3. 모든 노드 쌍에 대해, 한 노드를 거쳐 가는 비용이 기존의 비용보다 작으면 비용 정보를 갱신합니다.

하지만 플로이드-와샬 알고리즘의 시간 복잡도는 O(n^3)입니다. 이는 모든 노드 쌍에 대해 다른 노드를 거쳐 가는 비용을 검사하기 때문. 따라서, 노드의 수가 많은 그래프에서는 효율적으로 동작하지 않을 수 있습니다. 이런 경우에는 다익스트라 알고리즘 등 다른 알고리즘을 사용하는 것이 좋습니다.

파이썬으로 구현하는 플루이드-와샬

INF = float('inf')
# node는 노드의 수, edges는 간선 정보를 담은 리스트입니다. (출발 노드, 도착 노드, 비용) 형태로 저장되어 있습니다.
def floyd_warshall(node, edges):
    graph = [[INF] * node for _ in range(node)]
    
    for i in range(node):
        graph[i][i] = 0  # 자기 자신으로 가는 비용은 0
        
    for edge in edges:
        u, v, w = edge  # 출발 노드 u, 도착 노드 v, 비용 w
        graph[u][v] = w  # 간선 정보를 이용해 비용 갱신
        
    for k in range(node):
        for i in range(node):
            for j in range(node):
                # i에서 j로 가는 비용보다 i에서 k를 거쳐 j로 가는 비용이 더 작으면 갱신
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    return graph

자바로 구현하는 플루이드 와샬

import java.util.Arrays;

public class Main {
    final static int INF = 999999999;

    public static void floydWarshall(int[][] graph) {
        int n = graph.length;

        // 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)
                    graph[i][j] = 0; // 자기 자신으로 가는 비용은 0
                else if (graph[i][j] == 0)
                    graph[i][j] = INF; // 직접적으로 연결되지 않은 노드들은 INF로 설정
            }
        }

        // 플로이드-와샬 알고리즘 수행
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (graph[i][k] + graph[k][j] < graph[i][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }

        // 결과 출력
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == INF)
                    System.out.print("INF ");
                else
                    System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] graph = new int[][]{
            {0, 5, INF, 8},
            {7, 0, 9, INF},
            {2, INF, 0, 4},
            {INF, INF, 3, 0}
        };
        floydWarshall(graph);
    }
}