[Floyd-Warshall Algorithm] 에 관한 정리

플로이드 워셜 알고리즘(floyd Warshall Algorithm)은 대표적인 APSF(All pairs Shortest Path)알고리즘 중 하나입니다.

활용(Applications)
1. computer network
2. aircarft network
3. railroad network
4. table of distances between all pairs of cities for a road atlas

간단한 알고리즘의 속성
1. 그래프에서 가장 짧은 경로를 찾는 그래프 알고리즘
2. 그래프는 음의 가중치를 가져도 됨(Dijkstra's algorithm은 불가능)
3. 다이나믹 프로그래밍의 특성을 가짐(미리 계산된 최소경로를 이용해서 활용함)
4. O(N^3)의 시간 복잡도를 지님 (N은 노드의 개수)

[예시]

다음과 같은 가중치를 가진 그래프 G가 있습니다.

그래프 속 노드들 간의 거리를 인접행렬(Adjacency Matrix)로 표현하면 위와 같습니다.
이 이차원 배열을 D라고 합시다.

예를 들어 a열 b행의 값은 a노드에서 b노드까지의 거리를 2라고 표시한 것입니다.
d열 a행의 값은 무한대 입니다. 현재 a노드 입장에서는(a라는 노드에서 1인칭으로 바라본다면) d로 가는 직접적인 길이 없으니 무한대로 표시합니다.

Step 1
이번에는 a노드에서 어떤 노드를 가는 길을 계산할때 D[a][어떤노드]로만 계산하지 말고 D[a][k]+D[k][어떤노드]의 계산을 통해 k라는 노드를 거쳐가는 경우를 고려해서 최단거리를 갱신해보겠습니다.

k를 a노드에서 e노드까지 총 5개의 노드에 대해서 바꿔가면서 계산을 해보겠습니다.

Step(1/5) k=a 일때

D[c][e]= 현재 무한대 입니다(c->e=무한대)
이 상황에서 k가 a라고 하면
D[c][e]=D[c][k]+D[k][e]라고 할 수 있습니다.
기존의 값 무한대(D[c][e])에 비해 D[c][k]+D[k][e] 값인 7 인 더 적은 값이기 때문에 기존의 D[c][e]를 7로 업데이트 해줍니다.

D[c][b]= 현재 무한대입니다, D[c][b]=D[c][k]+D[k][b]이고 이 값은 6이기 때문에 기존의 D[c][b]도 6으로 갱신 해줄 수 있습니다.

이러한 과정을 모든 노드에 대해서 반복을 하면 모든 지점에서 모든 경로로 가는 최소 거리가 D배열에 갱신 됩니다.

[Pseudo Code]

[Code Ref.]

import pprint


n=int(input()) ##노드의 개수
e=int(input()) ##엣지의 개수
arr=[[float('inf') for i in range(n)] for i in range(n)] ## 거리배열 초기화 
for i in range(n):
    for j in range(n):
        if i==j: # i와 j 가 같으면 i->i 노드의 거리라는 의미와 같아서 자기 자신과의 거리는 0
            arr[i][j]=0
input=[list(map(int,input().split())) for i in range(e)]

for e in input:
    arr[e[0]-1][e[1]-1]=min(e[2],arr[e[0]-1][e[1]-1])



for l in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            arr[i][j]=min(arr[i][j],arr[i][l]+arr[l][j])# 기존의 값과 l 노드를 지나서 가는 경우의 값을 비교 최소 값으로 갱신


#여기까지 하면 arr 테이블의 거리는 최소 거리 갱신이 완료됨 

for i in range(len(arr)):
    for j in range(len(arr[0])):
        if arr[i][j]==float('inf'):
            print(0,end=' ')
        else:
            print(arr[i][j],end=' ')
    print()