모든 쌍의 최단 경로

모든 쌍의 최단 경로 알고리즘은 Floyd-Warshall 알고리즘이라고도 하며 주어진 가중치 그래프에서 모든 쌍의 최단 경로 문제를 찾는 데 사용됩니다. 이 알고리즘의 결과로 그래프의 모든 노드에서 다른 모든 노드까지의 최소 거리를 나타내는 행렬이 생성됩니다.

처음에 출력 행렬은 그래프의 주어진 비용 행렬과 동일합니다. 그 후 출력 행렬은 모든 정점 k를 중간 정점으로 사용하여 업데이트됩니다.

이 알고리즘의 시간 복잡도는 O(V3)이며, 여기서 V는 그래프의 정점 수입니다.

입력 - 그래프의 비용 매트릭스.

0 3 6 ∞ ∞ ∞ ∞ 3 0 2 1 ∞ ∞ ∞ 6 2 0 1 4 2 ∞ 1 1 0 2 ∞ 4∞ ∞ 4 2 0 2 1∞ ∞ 2 ∞ 2 0 1∞ ∞ ∞ 4 1 1 0

출력 - 모든 쌍의 최단 경로의 행렬입니다.

0 3 4 5 6 7 73 0 2 1 3 4 44 2 0 1 3 2 35 1 1 0 2 3 36 3 3 2 0 2 17 4 2 3 2 0 17 4 3 3 1 1 0

알고리즘

floydWarshal(비용)

입력 − 주어진 그래프의 비용 매트릭스.

출력 − 정점에서 정점 사이의 최단 경로에 대한 행렬입니다.

k에 대해 시작:=0에서 n, i에 대해 수행:=0에서 n, j에 대해 수행:=0에서 n, 비용[i,k] + 비용[k,j] <비용[i, j], 다음 비용[i,j] :=비용[i,k] + 비용[k,j] done done done 현재 비용 행렬 표시End

예시

#include#include
#define NODE 7#define INF 999using namespace std;//graphint의 비용 행렬 costMat[NODE][NODE] ={ {0, 3, 6, INF, INF , INF, INF}, {3, 0, 2, 1, INF, INF, INF}, {6, 2, 0, 1, 4, 2, INF}, {INF, 1, 1, 0, 2, INF , 4}, {INF, INF, 4, 2, 0, 2, 1}, {INF, INF, 2, INF, 2, 0, 1}, {INF, INF, INF, 4, 1, 1, 0 }}; 무효 floydWarshal(){ int 비용[노드][노드]; // 임의의 노드에서 임의의 노드까지의 최단 거리를 저장하도록 정의 for(int i =0; i 
출력
 
행렬:0 3 5 4 6 7 73 0 2 1 3 4 45 2 0 1 3 2 34 1 1 0 2 3 36 3 3 2 0 2 17 4 2 3 2 0 17 4 3 <3 1 10 /사전>