플로이드 와샬(Floyd Warshall)

출처: https://blog.naver.com/ndb796/221234427842

📔 플로이드 와샬(Floyd Warshall) 란

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. ( 출처: 위키백과 )

• 모든 정점에서 모든 정점으로의 최단 경로를 구하는 것!
  • 거쳐가는 정점을 기준으로 구한다.
  • 다이나믹 프로그래밍 기법을 이용
  • 다익스트라의 경우 한 정점에서 모든 정점까지 의 최단 경로
• 반복문이 3개이므로 시간복잡도는 O(N^3) 이다. 하지만 코드는 매우 간단하다.

📔 플로이드 와샬(Floyd Warshall) 구현

• 가중치 인접 행렬을 만든다.

• i 에서 j 로 갈 때의 가중치이다.
• inf는 무한대라는 뜻으로 i 와 j가 바로 이어져 있지 않다는 의미
• 이제 거쳐가는 정점을 기준으로 인접 행렬을 갱신한다.
• i 에서 k를 거쳐 j로 가는 것과 i 에서 바로 j로 가는것
  adj[i][k] + adj[k][j] 와 adj[i][j] 를 비교
• 둘 중 작은것으로 인접 행렬을 갱신한다.
• 모든 정점에 대해서 행하므로 3중 포문을 사용
• 결과 값은 아래와 같다

# 가중치 인접행렬  # 바로 연결이 안돼있는 경우 INF(무한대)
N = 4
INF = float('inf')
adj = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
]

print('가중치 인접 행렬')
for row in adj:
    print(row)
print()

# 거쳐가는 정점 k를  기준으로
for k in range(N):
    # 출발 정점 i 에서
    for i in range(N):
        # 도착 정점 j 까지
        for j in range(N):
            # i에서 k를 거쳐 j 까지 가는 것과 i에서 j까지 바로가는 것중 값이 더 작은 것으로 갱신
            adj[i][j] = min(adj[i][k] + adj[k][j], adj[i][j])

print('결과')
for row in adj:
    print(row)
print()