• 그래프에서 최단 거리를 구하는 알고리즘

• 동적 계획법의 원리를 이용해 알고리즘에 접근 | O(V³) |

• N = 1000 일 경우 플로이드-워셜 사용 불가
• N = 100, 200 정도일 때 주로 사용

핵심 이론

• A 노드에서 B노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것

• 색칠된 에지 경로가 1→5 최단 경로라면 1→4 최단 경로와 4→5 최단 경로 역시 색칠된 에지로 이뤄짐
• 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이뤄짐

도출한 플로이드-워셜 점화식

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

1. 리스트를 선언하고 초기화

• D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 리스트

2. 최단 거리 리스트에 그래프 데이터 저장

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