플로이드 워셜 알고리즘

• 모든 노드에서 다른 모든 노드까지의 최단경로를 모두 계산함
• 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행
  • 다익스트라와 다르게 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않음.
• 2차원 테이블에 최단 거리 정보를 저장
• DP 유형에 속함 (점화식에 맞게 3중 FOR문을 이용해서 2차원 테이블을 갱신)
• 노드의 계수가
• 밀집그래프(완전그래프에 가까운 그래프)인 경우 플로이드 워샬 알고리즘이 효율적이다.
  • 밀집그래프가 아닌 경우 다익스트라를 n번 돌리는게 빠르다
• O(n^3)의 시간복잡도로 다익스트라(인접행렬을 사용한 경우)의 시간복잡도와 동일하다
  • N이 100이면 → 100만이어서 가능, 500이어도 → 1억 2천 500만 이어서 try해볼 수 있다.
  • 그러나 플로이드 알고리즘은 매우 간단하여 다익스트라 알고리즘을 사용하는 것보다 효율적(코딩이 효율적이라는 뜻, 시간복잡도가 효율적이라는 뜻이 아니다!)이다
• 음의 가중치도 된다
• 노드의 갯수가 적은 경우 (500개 이하) 에 사용해야 함

 

💡음수 사이클 검출
자기 자신에게 가는 간선 거리 즉 dist[i][i] < 0 이면 음수 사이클을 가지고 있는 것

점화식

a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사

k에 모든 노드, 모든 노드 a to b → 3중 반복문이 된다

코드

파이썬

INF = int(1e9) # 무한을 의미하는 값으로 10억

n = int(input())
m = int(input())

graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1, n+1):
	for b in range(1, n+1):
    	if a==b:
        	graph[a][b]=0
 
# 각 간선에 대한 정보 입력받아, 그 값으로 초기화
for _ in range(m):
	# A에서 B로 가는 비용은 C
    a,b,c = map(int,input().split())
    graph[a][b] = c
 
 # 플로이드워셜 알고리즘
 for k in rangE(1,n+1):
 	for a in range(1,n+1):
    	for b in range(1,n+1):
        	graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
 
 # 수행 결과 출력
 for a in range(1, n+1):
 	for b in range(1, n+1):
    	if graph[a][b]==INF:
        	print("INFINITY", end=" ")
        else:
        	print(graph[a][b], end= " ")
    print()

 

자바

public class Main{
	
    public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억
    public static int n,m; // n : 노드의 개수, m : 간선의 개수
    public static int[][] graph = new int[501][501]; // 노드 개수의 최대는 500개라고 가정
    

	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();
        
        // 최단 거리 테이블을 모두 무한으로 초기화
        for(int i=0;i<501;i++){
        	Arrays.fill(graph[i],INF);
        }
        
        for(int i=1;i<=n;i++){
        	for(int j=1;j<=n;j++){
            	if(i==j){
                	graph[i][j]=0;
                }
            }
        }
        
        // 각 간선에 대한 정보 입력
        for(int i=0;i<m;i++){
        	int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            
            graph[a][b]=c;
        }
        
        // 플로이드 워셜 알고리즘 
        for(int k=1;k<=n;k++){
        	for(int a=1;a<=n;a++){
            	for(int b=1;b<=n;b++){
                	graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
                }
            }
        }
        
        // 결과 출력
        for(int a=1; a<=n; a++){
        	for(int b=1;b<=n;b++){
            	if(graph[a][b]==INF){
                	System.out.print("INFINITY ");
                }else{
                	System.out.print(graph[a][b] + " ");
                }
            }
            System.out.println();
        }
        
    }

}