[Algorithm] 플로이드-워셜

플로이드-워셜 (Floyd-warshall) 알고리즘은 앞서 알아본 다익스트라, 벨만-포드와 같이 그래프에서 최단 거리를 구하는 알고리즘이다.

 

• 모든 노드 간에 최단 경로를 탐색
• 음수 가중치 에지가 있어도 수행할 수 있음
• 동적 계획법(dp)의 원리를 이용해 알고리즘에 접근한다.
• 노드 수 -> V일 때 O(V^3)의 시간 복잡도를 가진다.

 

핵심 이론

 

• A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로이다.
• 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다.
• 위와 같은 원리로 아래와 같은 점화식을 도출할 수 있다.
  • D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

구현 방법

 

  1. 리스트를 선언하고 초기화하기

• D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 리스트라 정의
• S와 E의 값이 같은 칸은 0, 다른 칸은 INF로 초기화

 

  2. 최단 거리 리스트에 그래프 데이터 저장하기

• 출발노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때 D[S][E] = W 로 에지의 정보를 리스트에 입력한다.
• 이렇게 플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현한다

 

 

  3. 점화식으로 리스트 업데이트 하기

• 기존에 구했던 점화식을 3중 for문의 형태로 반복하면서 리스트의 값을 업데이트한다.

for 경유지 K에 관해 (1~N)
	for 출발노드 S에 관해 (1~N)
    	for 도착노드 E에 관해 (1~N)
        	D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

 

• 3에서 2로 가는 방법이 INF 였는데 3에서 1을 거쳐 2로 가는 방법이 5이기 때문에 업데이트
• 3에서 4로 가는 방법이 INF 였는데 3에서 1을 거쳐 4로 가는 방법이 7이기 때문에 업데이트
• 4에서 1로 가는 방법이 INF 였는데 4에서 2을 거쳐 4로 가는 방법이 4이기 때문에 업데이트

 

https://it-garden.tistory.com/247

 

• 1에서 3로 가는 방법이 INF 였는데 1에서 4을 거쳐 3로 가는 방법이 5이기 때문에 업데이트
• 2에서 3로 가는 방법이 INF 였는데 2에서 4을 거쳐 3로 가는 방법이 6이기 때문에 업데이트

 

 

import sys

INF = sys.maxsize

def Floyd_Warshall():
    dist = [[INF]*n for i in range(n)] 
    
    for i in range(n): # 최단 경로를 담는 배열 초기화
    	for j in range(n):
        	dist[i][j] = a[i][j]
            
    for k in range(n):
    	for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist
    
    
n = 4
a = [[0,2,INF,4],[2,0,INF,5],[3,INF,0,INF],[INF,2,1,0]]

dist = Floyd_Warshall()

for i in range(n):
	for j in range(n):
    	print(dist[i][j],end='')
        
    print()

 

• 완성된 리스트는 모든 노드 간의 최단 거리를 알려준다.
• 플로이드-워셜 알고리즘은 모든 노드 간의 최단 거리를 3중 for문을 이용해 구해주기 때문에 O(V^3)으로 시간 복잡도가 빠르지 않은 편
• 따라서, 일반적 플로이드-워셜 알고리즘의 경우 노드 개수의 범위가 다른 그래프에 비해 적게 나타나는 것을 알 수 있다.

 

참고

(https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)