[알고리즘] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
• 다익스트라와 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘 수행
  - 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 찾는 과정이 필요X
• 플로이드 워셜은2 차원 테이블에 최단 거리 정보를 저장
• 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속함
• 각 단계마다 특정한 노드 K를 거쳐 가는 경우를 확인
  - A에서 b로 가는 최단 거리보다 a에서 k를거쳐 b로 가는 거리가 더 짧은지 검사

점화식

성능 분석

• 각 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로 고려
• 총 시간 복잡도는 O(N^3)!
  

//최단 거리를 계산하는 반복문
for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (costs[i][k] + costs[k][j] < costs[i][j])
						costs[i][j] = costs[i][k] + costs[k][j];
				}
			}
		}