SPFA1 벨만포드, SPFA 시작점을 정해줬을 때, 최단경로 알고리즘. 가중치가 음수여도 가능하다 *모든 간선을 돌면서 그에 속하는 정점에 대한 dist를 초기화할 수 있다면 초기화 해주는 작업을 정점개수-1만큼 반복한다. O(EV) 필요한 것: int dist[MAX]{0} vector adj[MAX]; //혹은 vector edge 일반적인 코드. 음의 사이클 검출방법 int main() { int N, M, dist[MAX], st, en; fill(dist, dist + N, INF); vector adj[MAX]; dist[st] = 0; bool minusCycle = false; for (int k = 0; k < N; k++) { // (N-1)번의 루프, N번째루프에 갱신되면 음의사이클존재 //이하 두개의 for문 .. 2019. 8. 18. 이전 1 다음