Floyd-Warshall은 어떻게 작동하며 K는 무엇입니까?

Question

Floyd-Warshall algorithm을 이해하는 데 어려움을 겪고 있습니다. 나는 그것이 어떻게 작동하는지 안다. 나는 손으로 그것을하는 방법을 안다. 그러나 나는 컴퓨터를 통해 그것을 이해할 필요가있다. perceptive.

FOR k <-- 1 TO N DO 
    FOR i <-- 1 TO N DO 
     FOR j <-- TO N DO 
      IF Djk + Dkj < DiJ THEN 
       Dij <-- djk + dkj 

k, i 및 j은 반복에 대한 변수이며, 그것은 n 값까지 반복 처리, 그리고 그것이 중첩 루프의 를 추측 한 다음 각 노드에서 보이는 미만은 최단 경로를 찾아?

Answer 1

Floyd-Warshall에서 k의 상당히 단순화 된 의미는 그래프의 "중간 지점"입니다. 마지막 두 줄은 다음과 같이 해석 할 수 있습니다. "i에서 k까지, 그리고 k에서 j까지는 i에서 j까지의 경로를 통해 지금까지 발견 한 경로를 통해 얻을 수 있으면 i에서 j부터 k까지의 경로가됩니다. 새로운 최단 경로 ".

Answer 2

K는 중간 정점을 나타낸다. 그래서 외부 루프는 기본적으로 K 번째 꼭지점을 중간 정지 점이라고합시다. 내부 2 개의 루프는 인접 행렬의 각 항목을 검사하고 K (중간 정점으로 K 사용)가 정점 i에서 j까지의 거리보다 작은 지 확인합니다 (인접 항목의 위치 i, j에있는 번호 매트릭스). 거리가 더 작 으면 d [i, j]를 업데이트하십시오.