📂 알고리즘/최단 경로

플로이드-와샬(Floyd-Warshall) 알고리즘

1. 개념 🐕‍🦺  플로이드-와샬(Floyd-Warshall) 알고리즘이란 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 다익스트라(Dijkstra) 알고리즘과 다르게 음의 가중치를 허용한다는 게 특징이라고 할 수 있다.  다익스트라 알고리즘을 간단하게 설명하자면 출발 정점으로부터 모든 정점까지의 최단경로를 구하는 알고리즘이다. 다익스트라를 이용하여 플로이드-와샬 알고리즘을 구현한다고 하면 출발 정점을 모든 정점의 개수만큼 설정해 주면 된다.  순차 탐색 방법으로 다익스트라를 구현하면 O(V^2)이고, 모든 정점을 출발 정점으로 한다고 하면 O(V * V^2) = O(V^3)이 되게 된다. 플로이드-와샬 알고리즘의 시간복잡도 또한 O(V^3)으로 같다. 하지만 플로이드-와샬 알..

다익스트라(Dijkstra) 알고리즘

1. 기본 개념 🍄 1. 최단 경로 가중치 그래프에서 두 정점 사이의 경로들 중에서 가중치의 합이 최소가 되는 경로 2. 대표적인 최단 경로 알고리즘 다익스트라(Dijkstra) 벨만포드(Bellman-Ford) 플로이드 와샬(Floyd-Warshall) 정의 출발 정점로부터 모든 정점까지의 최단 경로를 구하는 알고리즘 출발 정점로부터 모든 정점까지의 최단 경로를 구하는 알고리즘 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘 특징 음의 가중치를 허용 X 음의 가중치를 허용 O 음의 가중치를 허용 O 사용하는 알고리즘 그리디 알고리즘 그리디 알고리즘 DP 알고리즘 시간복잡도 O(V ^ 2) 또는 O(E log V) O(V ^ 2) 또는 O(E log V) O(V ^ 3) 2. 다익스트라(..