Hani_Levenshtein

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

다익스트라 알고리즘은 하나의 시작점에서 주어진 모든 정점까지의 최단 경로의 길이를 알려주는 알고리즘으로, 간선의 가중치가 전부 양수인 경우에 한하여 적용할 수 있었습니다. 2020/08/31 - [알고리즘] - 최단 경로 알고리즘 - [1] 다익스트라 알고리즘 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 시작점이 정해져 있는 단일 시작점 알고리즘이지만, 음수 가중치에 있을 때에도 그래프 상의 모든 정점에 대한 최단 경로를 알아낼 수 있습니다. 이제 벨만-포드 알고리즘의 동작 과정을 예시로 알아보겠습니다 먼저, 시작점 1을 제외한 모든 정점의 최단 경로 길이를 Max 값으로 초기화 시켜줍니다. 시작점의 경로 길이는 0입니다. 정점 1에 붙어있는 모든 간선을 체크합니다. 1번 노드까지의 비용 + 1..