Floyd-Warshall은 어떻게 동적 알고리즘입니까?

Question

Floyd-Warshall 알고리즘은 동적이므로 항상 최적의 솔루션을 제공해야합니다.

• 반복 0 : - 그래서 저를 혼란 것은 이러한 최적의 솔루션의 성격이 알고리즘의 각 세그먼트 동안 무엇이며, 특히, 나는 다음과 같은 세 가지 질문을 이해하기 위해 노력하고있어 최적의 (즉, 정확한) 솔루션이 제공됩니다 전에 반복이 발생합니까?

• 반복 1 :이 반복이 끝날 때 최적의 (즉, 정확한) 솔루션이 제공됩니까?

• 반복 횟수 i (임의의 i> 0) : 이 반복이 끝날 때 최적의 (즉 정확한) 솔루션이 제공됩니까?

누구든지 이러한 우려 사항을 해결할 수 있습니까?

Answer 1

리콜 외부 루프 반복 k는 "중간"의 정점은 비록 j-i에서 후보로 갈 수있는 그러므로

for k in 0..N-1 
    for i in 0..N-1 
     for i in 0..N-1 
      g[i,j] = min(g[i,j], g[i,k]+g[k,j]) 

를 외부 루프 부분 용액의 0 번 반복 후 (어느 이 시점에서 수정되지 않은 인접성 행렬과 동일 함)은 i에서 j까지 직접가는 모든 최단 경로가 표현되는 최종 솔루션의 하위 집합을 나타냅니다.

첫 번째 정점 (인덱스 0)을 통과하는 최단 경로가 혼합에 추가됩니다.

반복 후 부분 솔루션에는 (1) 직접 또는 (2) {0..K-1} 집합의 하나 이상의 정점을 통과하는 최단 경로가 포함됩니다. 물론 K이 N에 도달하면 솔루션이 완료됩니다.

Answer 2

반복 횟수 : : 반복을하기 전에 얻은 최적 해는 노드를 통과하지 않고도 도달 할 수있는 노드를 포함합니다. 따라서 첫 번째 반복 전에는 노드 자체의 거리 만 알면 노드와의 거리는 0입니다.

반복 1 : 첫 번째 반복 후에 두 노드 사이의 거리가 있습니다. 가장자리로 직접 연결됩니다.

반복 내가 : iteration i 후에는 없습니다 더 i 이상의 가장자리에 의해 분리 된 두 노드 사이의 거리를해야합니다.