[알고리즘]동적 계획(Dynamic Programming)_최단거리 Floyd - Warshall

💡Floyd - Warshall 

-  모든 노드 ~ 모든 노드 사이의 최단거리를 구하기 위해 사용하는 알고리즘

   (다익스트라 알고리즘: 한 노드~ 모든 다른 노드 사이의 최단거리 구함)

-  D(a,b) = min(D(a,b), D(a,k)+D(k,b))

 

-

   step1. 어떤 경유지도 거치지 않고 출반~도착 최단거리 기본 테이블에서 시작

   step2. 각 출발~도착 경로에서 다른 노드(경유지)를 들른다고 생각하고 최단거리 구함

              만약 경유지를 들르지 않는 것이 더 최단거리면 D(a,b)를 선택해 그대로 유지, 경유지를 들리는 것이

              더 최단거리면 D(a,k)+D(k,b) 선택

              => 경유지(k) = 1부터 시작해서 4까지 업데이트 

  step3. 가장 마지막 테이블이 최종 결과 (배열에도 최종 결과가 저장)

   

 

void floyd(const int W[][], int D[][]){
	int i,j,k;
	D = W; //W는 경유지 거치지 않은 상태의 기본 최단거리
	for (int k = 0; k < N; k++) { //경유지 노드
			for (int i = 0; i < N; i++) { //출발 노드
				for (int j = 0; j < N; j++) { //도착 노드
					// k번째 노드를 거쳐가는 비용이 기존 비용보다 더 작은 경우 갱신
					// 또는 연결이 안되어있던 경우(INF) 연결 비용 갱신.
					D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
				}
			}
		}
}

- 해당 D 배열에는 최단거리의 경유지에 대한 정보는 없다. 따라서 P 배열을 만들어 경유지 표시도 가능

   (경유지 여러개인 경우 가장 큰 인덱스, 경유지 없는 경우 0)

- 최적화 원칙 적용X