SPFA (Shortest Path Faster Algorithm)

SPFA(Shortest Path Faster Algorithm) 라는 알고리즘은 벨만-포드 알고리즘과 유사하게 음수 가중치가 있을 때 사용가능한 단일 시작점 알고리즘입니다. 2020/09/07 - [알고리즘] - 벨만포드 알고리즘 벨만-포드 알고리즘은 총 E 개의 간선을 V 번 방문을 해서 O(VE) 의 시간 복잡도를 갖습니다. 하지만 SPFA 는 경로의 길이가 갱신된 정점에 인접한 간선에 대해서만 다음 방문에서 체크를 하기 때문에 같은 간선을 V 번 방문할 필요가 없어서 평균 시간 복잡도가 O(E) 입니다. 단, 경로의 길이가 갱신되지 않았다면 방문을 계속 해야하기 때문에 최악의 경우엔 O(VE) 의 시간 복잡도를 갖습니다. SPFA 의 동작 원리는 벨만-포드 알고리즘의 동작 원리와 비슷하므로 차이점..
알고리즘 2020. 9. 7. 22:54
1