플로이드 와샬 알고리즘 :: 마이구미
이번 글은 플로이드 와샬 알고리즘에 대해 다뤄본다. 동적계획법을 기반으로 구현되는 알고리즘이다. 위키백과의 정의를 보자. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든
mygumi.tistory.com
그래프에서 모든 꼭지점 사이의 최단 경로의 거리를 구하는 알고리즘. 최단경로를 찾기에 좋은 알고리즘이다. 시간복잡도는 O(n^3)
for (int k = 0; k < n; ++k) { // k : 거쳐가는 정점
for (int i = 0; i < n; ++i) { // i : 출발 정점
for(int j = 0; j < n; ++j { // j : 도착 정점
if(d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}i -> j 로 직접 가는것과 i -> k -> j 로 k를 거쳐서 가는것 중 어느 경로가 비용이 낮은지 비교하여 값을 구한다.
