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

* Python을 기준으로 합니다

---

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

- 개념

• 플로이드-워셜 알고리즘 : 최단 경로를 구하는 알고리즘 중 하나로, 존재하는 모든 노드에서 다른 노드로의 최단 경로를 모두 계산해야 하는 경우 사용함
  • 다익스트라와 달리 플로이드-워셜은 한 지점에서의 최단 경로가 아닌 모든 노드로의 경로를 반환함
    - 이때 벨만-포드와 비슷하게 음의 가중치가 있는 경우에서도 사용가능 하지만, $O(n^{3})$의 time complexity를 소모하는 단점이 있음
  • 플로이드-워셜 알고리즘은 다이나믹 프로그래밍으로써 구현되고, 다음의 점화식을 가짐:
    (Eq. 1) $D_{ab} = \min(D_{ab},  D_{ak}+D_{kb})$
    - 시작 노드 $A$에서 노드 $K$를 거쳐 다른 노드 $B$로 가는 거리 ($D_{ak}+D_{kB}$)가 시작 노드 $A$에서 다른 노드 $B$로 가는 거리 ($D_{ab}$)보다 짧으면 최단 거리 값을 갱신함
  • 플로이드-워셜 알고리즘의 동작
    1. 그래프의 가중치로 2차원 배열을 초기화함
    2. 각 노드에 대해 시작 노드에서 해당 노드를 거쳐 다른 노드로 가는 모든 비용(거리)을 계산
    3. 새로 계산된 거리가 현재 거리보다 짧으면 2차원 배열을 업데이트함
    4. 모든 노드들에 대해 위 2~3번 과정을 반복

플로이드-워셜의 동작

- 구현

1. 플로이드-워셜 알고리즘의 구현

• 플로이드-워셜 알고리즘은 다이나믹 프로그래밍을 활용하고, 모든 노드에 대한 최단 거리를 반환함

import sys

INF = sys.maxsize

def floyd_warshall(graph):
  #다이나믹 프로그래밍
  dp = [[INF]*5 for _ in range(5)] #최대값으로 초기화

  for a in range(5):
    for b in range(5):
      if a==b: #자기자신으로의 거리는 0
        dp[a][b] = 0

  for a in range(5):
    for b, cost in graph[a]:
      dp[a][b] = cost #그래프의 값으로 dp 초기화

  #플로이드-워셜
  for k in range(5): #노드개수 만큼 반복
    for a in range(5): #노드개수 만큼 반복
      for b in range(5): #노드개수 만큼 반복
        dp[a][b] = min(dp[a][b], dp[a][k]+dp[k][b]) #점화식 D_ab = min(D_ab, D_ak+D_kb)
  
  return dp

• 결과 확인

#인접 리스트 형식 그래프
graph = [
    [(1,4),(2,3),(4,-6)],
    [(3,5)],
    [(1,2)],
    [(0,7),(2,4)],
    [(2,2)]
]

#플로이드-워셜
result = floyd_warshall(graph)
for row in result:
  print(row)

'''
[0, -2, -4, 3, -6] : 시작 노드를 0으로 했을 때 각 노드로의 최단 거리
[12, 0, 8, 5, 6]   : 시작 노드를 1로 했을 때 각 노드로의 최단 거리
[14, 2, 0, 7, 8]   : 시작 노드를 2로 했을 때 각 노드로의 최단 거리
[7, 5, 3, 0, 1]    : 시작 노드를 3로 했을 때 각 노드로의 최단 거리
[16, 4, 2, 9, 0]   : 시작 노드를 4로 했을 때 각 노드로의 최단 거리
'''