목록최단거리 (1)

별집사의 IT세상

Floyd 알고리즘

최단경로 구하는 그래프이론에 쓰이는 알고리즘이다. 포문을 삼중으로 돌려A에서 B로 가는데 C를 거치는 경로가 더 작다면 arr[A][C] > arr[A][B] + arr[B][C], 값을 작은 값으로 갱신하는 방식이다. 모든 경우의 수를 다 돌려서 가장 작은 값들로 리셋 시키는 방식, 시간복잡도는 O(n^3)이다. int i, j, k; for(j = 0; j dist[i][j] + dist[j][k])dist[i][k] = dist[i][j] + dist[j][k]; }}}
IT/IT 정보 2017. 4. 15. 02:18
Prev 1 Next