JUINTINATION

APSP(All-pairs shortest paths) 알고리즘이란? 어떤 그래프에서 모든 노드(시작 노드)부터 각각의 노드(도착 노드)까지의 모든 최단거리를 구하는 알고리즘이다. 여러 APSP 알고리즘 중에서 2가지를 살펴보겠다. 모든 정점에서 SSSP 알고리즘 실행하기 모든 정점에서 SSSP 알고리즘을 실행해야 하기 때문에 |V| 만큼 시간 복잡도가 증가한다. Dijkstra’s algorithm(음의 간선 X): O(|V||E| + |V|² log |V|) Bellman-Ford algorithm(음의 간선 O, 음의 사이클 X): O(|V|²|E|) DAG Shortest Path using Topological Sort: O(|V|² + |V||E|) 음의 사이클이 존재하지 않는 경우 Floyd..