플로이드-워셜(Floyd-Warshall)

### Floyd-Warshall(플로이드-워셜) ###

: 그래프에서 모든 정점간 사이의 최단 거리 찾기

=> 모든 최단경로 구하기 == 모든 정점 최단 경로 알 수 있다.

 

+ 모든 경로를 돌아보는 것으로 왔다갔다한 것을 다 알 수 있다.

​

시간 복잡도: O(n^3)

 

for i in range(n):
    for j in range(n):
        for k in range(n):
            if dist[j][k] > dist[j][i] + dist[i][k]
                dist[j][k] = dist[j][i] +dist[i][k]