플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.

2. 동적 계획 법의 원리를 이용해 알고리즘에 접근 | O(V^3) |

플로이드-워셜의 핵심 이론

• A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K 노드가 존재 한다면, 그것을 이루는 부분 경로 역시 최단 경로이다.
• 점화식 : D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

1. 배열을 선언하고 초기화 하기

• D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열
• S와 E의 값이 같은 칸은 0, 다른 칸은 무한대로 초기화한다.

1. 최단 거리 배열에 그래프 데이터 저장하기

• 출발 노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때, D[S][E] = W로 에지의 정보를 배열에 입력한다.

1. 점화식으로 배열 업데이트 하기

• 기존에 구했던 점화식을 3중 for문의 형태로 반복하면서 배열의 값을 업데이트 한다.

for 경유지 K에 관해 (1~ N)

for 출발 노드 S에 관해 (1~N)

for 도착 노드 E에 관해 (1~N)

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

→ 시간 복잡도가 빠르지는 않은 편이다.