Floyd Warshall (플로이드 와샬) 알고리즘

Floyd Warshall 

• 모든 정점에서 모든 정점으로의 최단 경로를 찾는 알고리즘
• Dijkstra 알고리즘과 다르게 한 장점으로부터 모든 정점으로의 최단경로가 아닌 모든 정점 사이의 최단경로를 구한다는 점과 음수 가중치가 있어도 최단 경로를 구할 수 있다점에서 다익스트라 알고리즘과 차이점이있다.

 

최단경로 찾는 과정

• 출발지에서 목적지로 가는 경우와 출발지에서 경유지를 통해 목적지를 가는 경우를 비교해 둘 중 더 빠른 경우가 존재한다면 더 빠른 경우로 최단 거리를 계산한다.

 

구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int[][] distance;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
 
        distance = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for (int j = 0; j < N; j++) {
                distance[i][j] = Integer.parseInt(st.nextToken());
                if (i != j && distance[i][j] == 0)
                    distance[i][j] = 99999;
            }
        }
        // 경유지 -> 출발지 -> 목적지 순
        for (int k = 0; k < N; k++) { //경유지
            for (int i = 0; i < N; i++) { //출발지
                if (i == k) continue;
                for (int j = 0; j < N; j++) { //도착지
                    if (distance[i][k] + distance[k][j] < distance[i][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                    }
                }
            }
        }
 
        System.out.println("================ folyd warshall ================ ");
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(distance[i][j] + " ");
            }
            System.out.println();
        }
 
    }
 
}

<결과>