동적 계획 알고리즘(1)[플로이드 모든 쌍 최단 경로 알고리즘]

동적 계획 알고리즘은 부분 문제들을 모두 해결한 후, 그 해들을 이용하여 큰 크기의 부분문제들을 해결하여 최종적으로 전체를 해결하는 알고리즘이다.

 

동적 계획 알고리즘은 부분문제들 사이 간에 영향을 미칠 수 있음. 

 

분할 정복 알고리즘은 서로 따로 값들을 계산했다면, 

여기서는 앞선 부분문제의 결과가 다른 부분문제의 계산에 이용될 수 있음.(의존적 관계)

 

---

<슈도 코드>

 

AllPairsShortest

입력: 2차원 배열 D, 단, D[i,j]=간선 (i,j)의 가중치, 만일 간선(i,j)이 존재하지 않으면 D[i,j]=∞, 모든 i에 대하여 D[i,i] = 0이다.

출력: 모든 쌍 최단 경로의 거리를 저장한 2차원 배열 D

1  for k = 1 to n

2      for i = 1 to n (단, i != k)

3          for j = 1 to n (단, i != k)

4            D[i,j] = min{D[i,k]+D[k,j],D[i,j]}

 

 

모든 점을 경유 가능한 점들로 고려된 모든 쌍 i와 j의 최단 경로의 거리를 찾는 방식.

 

시간 복잡도는 삼중for문이 돌아감으로 인해 O(n^3)

---

<과정 그려보기>

앞에서 최소값으로서 갱신된 부분들은 2차월 배열 D에 반영된 후 반복문이 계속 돌아감.