최단 경로 (3)
Shortest Path (3) Floyd-Warshall Algorithm- all-to-all 최단 경로 알고리즘들 중 가장 유명하다.- Floyd 알고리즘은 동적 계획법(Dynamic Programming) 전략에 기반하고 있다.- 가중치 방향 그래프 G = (V, E) (V = {1, 2, ... , n})- 모든 노드 쌍들간 최단 경로의 길이를 구한다.- $d^k$[i, j]중간에 노드 집합 {1, 2, ... , k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단 경로의 길이를 뜻한다.1) $d^0$[i, j]는 k가 0인 경우로 공집합을 의미한다. 또한 중간에 지날 수 있는 노드가 없다는 것으로 직접 연결된 엣지가 있지 않다면 길이를 ∞로 생각한다.2) $d^n$[i, j]는 k가 n..
