FandPROG FandPROG

플로이드-와샬(Floyd-Warshall) 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 특히 음의 가중치가 포함된 그래프에서도 동작하지만, 음의 사이클(negative cycle)이 있으면 고장난다.플로이드 와샬의 기본 개념플로이드 와샬은 기본적으로 Dp(Dynamic Programming)알고리즘을 사용하는 알고리즘이다. 플로이드 와샬의 핵심은 "거쳐가는 경로"이다. 플로이드 알고리즘은 "dp[i][j][k] = "i에서 j사이 거쳐가는 모든 정점의 번호가 k 이하인 최단거리"를 기반으로 둔 것이다.  그래프 표현:그래프는 일반적으로 n x n 크기의 인접 행렬로 표현된다. 여기서 n은 그래프의 정점의 수이다. 이 행렬의 각 요소 Floyd[i][j]는 정점 ..