최단 경로

다익스트라(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. 다익스트라(..