플로이드 워셜 알고리즘 ( Floyd-Warshall Algorithm)

플로이드 워셜 알고리즘

• 다익스트라가 한 지점에서 다른 지점까지의 최단 경로를 구한다면,
  플로이드 워셜은 모든 지점에서 다른 모든 지점까지의 최단 경로를 구한다.
• dynamic programming기법중 하나이다.
• dist[ i ][ j ] = min( dist[ i ][ j ] , dist[ i ][ k ] + dist[ k ][ j ] )
  • 핵심 아이디어는 정점 k를 거쳐가는 경로와 직접 이동하는 경로를 비교해서, 최단경로를 업데이트 하는것.
  • dist[ i ][ j ]  : 정점 i에서 정점 j까지의 최단 거리
  • dist[ i ][ k ] : + dist[ k ][ j ] :  k를 거쳐서 가는 경로의 거리이다.
• 시간 복잡도가 (정점_개수)^3 이다.
  • 그래서 정점의 갯수가 적을때 적합하며, E logv의 시간 복잡도를 가진 다익스트라 보다 느리다.

INF = float('inf')
graph = [
    [0,    4,    INF, 10], 
    [INF,  0,    3,   INF],
    [INF,  INF,  0,   1],   
    [INF,  INF,  INF, 0]    
]

def floyd_warshall( graph ):
    n = len(graph)
    dist = [ [graph[i][j] for j in range( n ) ] for i in range( n) ]
    print(f'초기화한 거리 행렬 출력.. {dist}')
    for k in range ( n ):
        for i in range( n ):
            for j in range( n ):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min( dist[i][j] , dist[i][k] + dist[k][j] )

    return dist

rst = floyd_warshall( graph )
print("플로이드 워셜 결과 " )
for row in rst:
    print(row)