[최단 경로] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드 워셜 알고리즘 개요

플로이드 워셜 알고리즘은

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다
• 다익스트라 알고리즘과 마찬가지로, 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 그러나, 아래 두 가지에서 다익스트라와 차이가 있다. 
  • 다익스트라 알고리즘은 한 시작점에서 다른 정점까지의 최단 거리를 구하는데 반해 플로이드 알고리즘은 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구할 수 있다.
  •  음의 가중치를 가지는 그래프에서도 쓸 수 있다
• 플로이드 알고리즘은 2차원 테이블에 최단 거리 정보를 저장한다.

 

플로이드 워셜 알고리즘

• 각 단계마다 특정 한 노드 k를 거쳐가는 경우를 확인한다.
  • a에서 b로 가는 최단거리보다, a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.
  • 점화식은 다음과 같다.

 

 

 

 

동작 과정 살펴보기

[초기상태] 그래프를 준비하고, 최단거리 테이블을 초기화

• 처음에는 각 노드를 기준으로, 현재 노드와 인접한 노드들을 확인하여 테이블 갱신
  • 행 : 출발노드
  • 열 : 도착노드 의미
• 이후, 1번노드~4번노드 각각에 대해, 각 노드를 거쳐가는 경우를 고려해서, 테이블 갱신

 

[Step1 ] 1번 노드를 거쳐가는 경우를 고려해서, 테이블 갱신

• 하늘색은 step1을 통해 갱신되는 부분을 의미함
  • 1번 노드를 거쳐가는 경우를 확인하고 있기 때문, 시작지점이 1인 경우(1행)와, 도착지점이 1인 경우(1열)은 색칠되어있지 않다
  • 또한, 자기자신-자기자신으로 가는 경우는 갱신되지 않는다고 가정 → 대각선 색칠 x
  • ex) 2번 노드→4번 노드의 경우, 원래는 ‘무한’이었지만, 1번 노드를 거쳐가는 순간 거리가 9로 갱신된 것을 확인할 수 있다.

 

[Step2 ] 2번 노드를 거쳐가는 경우를 고려해서, 테이블 갱신

 

• 하늘색은 step2을 통해 갱신되는 부분을 의미함
  • 2번 노드를 거쳐가는 경우를 확인하고 있기 때문, 시작지점이 2인 경우(2행)와, 도착지점이 2인 경우(2열)은 색칠되어있지 않다
  • 또한, 자기자신-자기자신으로 가는 경우는 갱신되지 않는다고 가정 → 대각선 색칠 x

 

[Step3 ] 3번 노드를 거쳐가는 경우를 고려해서, 테이블 갱신

• ex) 4번 노드→1번 노드의 경우, 원래는 ‘무한’이었지만, 3번 노드를 거쳐가는 순간 거리가 2+5 = 7로 갱신된 것을 확인할 수 있다.

 

[Step4 ] 4번 노드를 거쳐가는 경우를 고려해서, 테이블 갱신

 

 

 

코드

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

n = int(input) #노드의 개수 입력받기
m = int(input) #간선의 개수 입력받기



#2차원 리스트를 만들고, 무한으로 초기화

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


#자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
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


#점화식에 따라 플로이드-워셜 알고리즘 수행(3중 for문)
for k in range(1,n+1): # k는 거쳐가는 노드
  for a in range(1,n+1): # a는 출발 노드
    for b in range(1,n+1): # b는 도착 노드
      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):
    # 도달할 수 없는 경우, 무한(INFINITY) 이라고 출력
    if graph[a][b] == INF:
      print("INFINITY", end=" ")
    else:
      print(graph[a][b], end = " ")
  print()

 

 

플로이드-워셜 알고리즘 성능 분석

• 노드의 개수가 N개일 때, 알고리즘상으로 N번의 단계(각 노드를 거쳐가는 단계)를 수행한다
  • 각 단계마다 O(N^2)의 연산을 통해, 현재 노드를 거쳐 가는 모든 경로를 고려(3중 반복문으로 구현)
• 따라서, 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)
  • 플로이드 워셜이 사용되어야 하는 경우 → 노드의 갯수가 500개 이하로, 작은 경우가 많다 (시간초과 판정 안받으려면)
• 따라서, 노드의 갯수가 충분히 크다면, 최단거리를 구하는 문제에서 보통 다익스트라를 사용한다

 

다익스트라 vs 플로이드 워셜

• 다익스트라 알고리즘
  • 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘
• 플로이드-워셜 알고리즘
  • 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우

다익스트라플로이드-워셜

 

다익스트라	플로이드
한 지점에서 다른 특정 지점까지의 최단 경로	모든 지점에서 다른 모든 지점까지의 최단 경로
- 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행 - 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택 - 이후 해당 노드를 거쳐가는 경로를 확인하며 최단 거리 테이블을 갱신	- 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행 - 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다(다익스트라는 필요했)
1차원 리스트에 최단거리 저	2차원 테이블에 최단 거리 정보 저장

 

 

 

Reference

https://www.youtube.com/watch?v=hw-SvAR3Zqg