플로이드 워셜 알고리즘

알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

📌 플로이드-워셜(Floyd-Warshall) 알고리즘이란?

• 모든 최단 경로를 구하는 알고리즘

다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다.

• 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다.

 

시간 복잡도 : O(n^3)

 

 

 

 

 

 

예제

---

프로그래머스 - 합승 택시 요금

 

 

 

import java.util.*;

class Solution {
    static final int INF = 987654321;

    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = INF;
        int dist[][] = new int[n+1][n+1];
        for(int i=0; i<n+1; i++){
            Arrays.fill(dist[i], INF);
        }

        for(int i=0; i<fares.length; i++){
            int c = fares[i][0];
            int d = fares[i][1];
            int f = fares[i][2];
            dist[c][d] = f;
            dist[d][c] = f;
            
        }
        
        for(int k=1; k<n+1; k++){
            for(int i=1; i<n+1; i++){
                for(int j=1; j<n+1; j++){
                    if(i==j) dist[i][j] = 0;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        for(int i=1; i<n+1; i++){
            if(dist[s][i] != INF && dist[i][a] != INF && dist[i][b] != INF){
                answer = Math.min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
            }
        }
        
        return answer;
    }
}

 

 

---

프로그래머스 - 배달

 

class Solution { 
    public int solution(int N, int[][] road, int K) {
        int[][] arr = new int[N][N];        
        int answer = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(i == j) {
                    continue;
                }                
                arr[i][j] = 500001;
            }
        }
    
        for (int i = 0; i < road.length; i++) {
            if(arr[road[i][0]-1][road[i][1]-1] > road[i][2]) {
                arr[road[i][0]-1][road[i][1]-1] = road[i][2];
                arr[road[i][1]-1][road[i][0]-1] = road[i][2];
            }
        }
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    if(arr[j][k] > arr[j][i] + arr[i][k]) {
                        arr[j][k] = arr[j][i] + arr[i][k];
                    }
                }
            }
        }
        
        for (int i = 0; i < N; i++) {
            if(arr[0][i] <= K) {
                answer++;
            }
        }   
        
        return answer;
    }
}