다익스트라 vs 플로이드 워샬

항목	다익스트라 알고리즘	플로이드 워셜 알고리즘
📌 목적	단일 출발점에서 다른 모든 정점까지의 최단 경로	모든 정점 쌍 간의 최단 경로
🔁 반복 방식	출발점을 바꿔서 여러 번 실행해야 모든 쌍 구할 수 있음	한 번의 알고리즘으로 모든 쌍 계산
⛔️ 음의 가중치	음의 가중치 불가능 (음수 간선이 있으면 틀림)	음의 가중치 허용, 단 음의 사이클은 불가능
⏱️ 시간 복잡도	$O((V + E) \log V)$ (우선순위 큐 사용 시)	$O(V^3)$
📊 그래프 크기	정점 수가 많고 간선이 적은 그래프에 적합	정점 수가 작을 때 적합 (보통 100 이하)
📥 구현 복잡도	상대적으로 복잡	비교적 단순 (삼중 for문)

음의 가중치가 만약 등장하게 되면, 기본적으로 다익스트라는 양의 가중치에서만 풀 수 있었잖아요? 애당초 음의 가중치에서 해결할 수 없는...