DongDD's IT

Floyd-Warshall(플로이드 와샬) 알고리즘 Floyd-Warshall Algorithm - 그래프에서 모든 정점 사이의 최단 거리를 구하기 위한 알고리즘- 다익스트라 알고리즘을 모든 정점에서 수행한 것과 같은 알고리즘이지만 플로이드 와샬 알고리즘은 구현이 간단하다.- 음수 가중치에 대한 처리가 어려운 다익스트라 알고리즘에 비해 플로이드 와샬 알고리즘은 사이클이 없는 경우 음수 가중치 처리가 가능하다. Floyd-Warshall Complexity - 단순히 반복문 3개를 vertex만큼 돌기 때문에 O(V^3)의 시간 복잡도를 갖는다.- 특정 정점에서 특정 정점까지의 경로를 저장해나가며 구한 경로를 이용해 새로운 최단 경로를 찾는 DP방식으로 수행된다. 그러므로 2차원 배열이 필요하므로 O(V^..