SPFA(Shortest Path Faster Algorithm) 은 벨만포드 알고리즘을 개선한 알고리즘이다. v - 1번 반복하는 동안 매 반복마다 모든 간선에 대해서 간선 경감을 진행하는 대신, 간선 경감이 일어나는 정점에 대해서만 그 정점에 연결된 간선들에 대해서 다음 간선 경감을 진행하는 방식이다. 최악의 경우 O(V^3) 의 시간복잡도를 갖지만, 평균적으로 O(E) 의 시간복잡도를 갖는다. https://www.acmicpc.net/problem/11657 package 최단경로.spfa.타임머신; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.A..