최단경로
-
[알고리즘/다익스트라] 다익스트라(Dijkstra) 알고리즘Mhwan's Study/Algorithms 2021. 1. 15. 04:10
그래프를 탐색하는 알고리즘에는 대표적으로 DFS, BFS가 있고 이들은 모두 간선을 이용할때 가중치가 없는 경우이다. 특히 BFS의 경우 가중치가 없는 경우 최단경로를 구할때 사용하지만 노드 사이의 간선을 이용할 때 가중치가 있는 그래프가 있고, 시작점으로 부터 목적지까지의 최소한의 가중치 비용을 갖는 최단 경로를 계산해야할 때는 다익스트라 알고리즘, 플로이드-와샬 알고리즘, 벨만-포드 알고리즘을 사용해야합니다. 오늘부터 이 세개의 알고리즘을 공부하며 포스팅 할 계획으로, 다익스트라 알고리즘부터 시작하겠습니다. 먼저, 다익스트라 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 거리를 구할 수 있습니다. 단, 간선의 비용은 음수이면 안됩니다. (음수의 간선일 경우 플로이드-와샬 알고리즘을 사용합니다..