Floyd Warshall

Floyd Warshall 알고리즘 *거쳐가는 노드!!

FW알고리즘은 다익스트라 알고리즘 처럼 최단 거리를 찾는 알고리즘이다.
다익스트라와의 차이라고 한다면 다익스트라는 한 정점에서 다른 모든 정점까지의 최단거리를 구하는데 반해 FW는 모든 정점에서 다른 모든 정점까지의 최단거리를 구한다. FW의 시간복잡도는 O(V^3)이다.
출발노드에서 바로 도착 노드로 가는 경우와 (출발 -> 거쳐가는 노드) + (거쳐가는 노드 -> 도착)과 비교하는것이 메인 아이디어 이다.

public class Main
{
    static int num = 4;
    static int INF = 100000000; // 연결되어있지 않은 경우
    
    static int[][] a = {
        {0,5,INF,8},
        {7,0,9,INF},
        {2,INF,0,4},
        {INF, INF, 3,0}
    };
    
    static void floyd_warshall()
    { 
        // 결과 배열. 원본 크기 만큼
        int[][] d = new int[num][num];
        // 먼저 초기 그래프와 동일하게 만들어줌
        for (int i=0; i< num; i++)
        {
            for (int j=0; j<num; j++)
            {
                d[i][j] = a[i][j];
            }
        }
        
        /* 출발노드에서 바로 도착 노드로 가는 경우와
        (출발 -> 거쳐가는 노드) +  (거쳐가는 노드 -> 도착)과 비교
        2번->3번 vs 2번->1번 + 1번 + 3번
        */
        // 3중 for문 이용해 구현
        // k = 거쳐가는 노드
        for (int k=0; k<num; k++)
        { // i = 출발 노드
            for (int i=0; i<num; i++)
            { // j = 도착 노드
                for (int j=0; j<num; j++)
                {
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                    // d[i][j]는 i에서 j로 한번에 가는 경우
                }
            }
        }
        
        // 결과 출력
        for (int i=0; i<num; i++)
        {
            for (int j=0; j<num; j++)
            {
                System.out.print(d[i][j]+" ");
            }
            System.out.println();
        }
        
    }
    
	public static void main(String[] args) 
	{
		floyd_warshall();
	}
}