시작하기 전에그래프에서 최단 경로를 찾는 알고리즘은 크게 세 가지가 존재한다고 알고 있었다. Dijkstra- 시작점이 존재해야 함. 그래프의 간선 가중치가 음이 아닌 정수일 때만 가능Floyd-Warshall- 모든 정점 쌍 사이의 최단 경로를 구할 때 사용, 음수 가중치 및 음의 사이클 판별 가능Bellman-Ford- 시작점이 존재해야 함. 음수 가중치 및 음의 사이클 판별 가능 Claude 선생님과 함께 알고리즘 복습을 하던 중에 SPFA라는 것을 접하게 되었다.SPFA 또한 그래프에서 최단 경로를 찾는 알고리즘이며, 이를 알기 위해선 Bellman-Ford를 먼저 알아야 한다.여기서는 Bellman-Ford의 원리만 간단히 설명하겠다.Bellman-Ford정점이 $N$개인 그래프의 어떤 최단 경..