음의 가중치

플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘임기능특징시간복잡도 (노드 수:V)모든 노드 간에 최단 경로 탐색음수 가중치가 있어도 수행 가능DP의 원리를 이용해 알고리즘에 접근O(V³)핵심 이론플로이드 워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A노드에서 B노드까지 최단 경로를 구했다고 가정. 최단 경로 위에 k노드가 존재한다면, 그것을 이루는 부분 경로 역시 최단 경로라는 것.색칠된 경로가 `1→5`의 최단 경로라면, `1→4` 최단 경로와 `4→5` 최단 경로 역시 색칠된 경로로 이루어질 수 밖에 없음즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로 조합으로 이루어진다는 의미이므로다음과 같은 점화식을 도출 가능 함.📌 도출한 플로이드 워셜 점화식D[S][E] = Math.m..