floyd warshall의 노드 간 거리

Question

This wikipedia 페이지에서는 그래프에서 노드 간의 최단 경로를 찾기 위해 Floyd Warshall 알고리즘을 설명합니다. 위키 피 디아 페이지는 이미지 의 왼쪽에있는 그래프를 시작 그래프로 사용하고 (k = 0 일 때 첫 번째 반복 이전에) 나머지 반복 (k = 1 등)을 표시하지만 그 그래프의 중요성을 설명하지는 않습니다. 노드 사이의 수와 그 수의 계산 방법. 예를 들어, 시작 그래프에서 k = 0 일 때 1과 3 사이의 가장자리에 -2가있는 이유는 무엇이며 왜 2와 3 사이의 가장자리에 3이 있습니까? 어떻게 계산됩니까?

또, K = 2는 상기 위키 페이지라고하면

[2,1,3]가 최단 경로 매우 발생되기 때문에 [4,2,3]이 고려되지 않은 경로 2에서 3까지입니다.

왜 [2,1,3]이 [4,2,3]보다 짧습니까?

Answer 1

가장자리의 숫자는 단지 무게입니다. 그것은 입력의 일부입니다. 알고리즘은 그것들을 계산하지 않습니다. [2, 1, 3]은 [4, 2, 3]보다 짧지 않다. 그것은 [2, 3]보다 짧습니다. 그게 유일한 문제입니다.