플로이드 워셜 알고리즘 . 3

플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다

 

플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다는 점에서 점화식에 맞게 
3중 반복문을 이용해서 2차원 테이블을 갱신한다

 

3중 반복문을 이용하기 때문에 시간복잡도가 O(N^^3) 이기에 노드의 개수가 적은 상황에서 효과적으로 사용할 수 있고
노드의 개수, 간선의 개수가 많은 경우에는 일반적으로 다익스트라 알고리즘을 사용해야 해결할 수 있는 경우가 많다

 

 

 

플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형이기 때문에 점화식을 동반한다

 

 

 

 

 

(중간 생략)

 

 

 

 

 

 

플로이드 워셜 알고리즘을 사용해야 하는 경우 노드의 개수가 500개 이상으로는 주어지지 않는 경우가 많다. 
3중 반복문을 사용해서 시간복잡도가 O(N^^3) 이기 때문이다

 

 

 

자바에서 최솟값을 알려주는 함수는 Math.min() 함수이다

 

 

 

플로이드 워셜 알고리즘을 사용해야 하는 경우 노드의 개수가 500개 이하로 주어지는 경우가 많다
그런데 시간 제한이 넉넉하지 않다면 이마저도 시간 초과가 될 수 있다
그렇기에 문제를 본 후 이 문제를 다익스트라로 풀어야 편한지, 플로이드 워셜로 풀어야 편한지 잘 판단해야 한다