1. 개념 그래프 상에 있는 모든 경로의 최단 경로를 구할 수 있는 알고리즘이다. 즉, 노드 1 2 3 4 5 가 있을 때, 노드 1과 노드 2사이의 최단 경로, 노드 1과 노드 3 사이의 최단 경로....노드 4와 노드 5 사이의 최다 경로를 모두 구할 수 있다. 출발 노드로부터 각 노드까지의 최단 경로를 구하는 다익스트라나 벨만포드 알고리즘과는 살짝 다르다. 2. 특징 모든 노드 간의 최단 경로를 탐색할 수 있다. 음수 가중치 에지가 있어도 수행할 수 있다. 동적 계획법의 원리를 이용해 알고리즘에 접근한다. 시간 복잡도가 O(V3)이다. V는 노드의 수. 인접 행렬을 이용하면 구현이 간단하다. 3. 원리 동적 계획법의 원리 시작 노드부터 도착 노드까지의 최단 경로는 시작 노드부터 중간 노드까지의 최단..