다익스트라
-
[알고리즘/벨만포드] 벨만-포드(Bellman-Ford) 알고리즘Mhwan's Study/Algorithms 2021. 1. 23. 03:12
벨만-포드 알고리즘은 이전에 한 다익스트라 알고리즘처럼 단일 시작점에서 모든 정점까지의 최단거리를 구하는 알고리즘입니다. 이 알고리즘은 다익스트라와 달리 가중치가 음수인 간선을 포함하는 그래프에서 최단 경로를 정확히 구할 수 있고, 음수인 사이클을 판별해낼 수 있습니다. 다익스트라 알고리즘에 비해 시간복잡도가 좋지 않으므로, 음수인 간선을 갖는 그래프나 음수인 사이클을 판별할 때 사용하는 것이 좋습니다. # 완화 (Relaxation) 이 알고리즘의 가장 핵심이 되는 특성입니다. u에서 v까지의 최단거리 dis[v] cur.weight + nextNode.weight이 만족할 경우에만 우선순위 큐에 넣었습니다. 1 2 3 4 5 6 7 for (Node nextNode : graph.sparseList...
-
[알고리즘/다익스트라] 다익스트라(Dijkstra) 알고리즘Mhwan's Study/Algorithms 2021. 1. 15. 04:10
그래프를 탐색하는 알고리즘에는 대표적으로 DFS, BFS가 있고 이들은 모두 간선을 이용할때 가중치가 없는 경우이다. 특히 BFS의 경우 가중치가 없는 경우 최단경로를 구할때 사용하지만 노드 사이의 간선을 이용할 때 가중치가 있는 그래프가 있고, 시작점으로 부터 목적지까지의 최소한의 가중치 비용을 갖는 최단 경로를 계산해야할 때는 다익스트라 알고리즘, 플로이드-와샬 알고리즘, 벨만-포드 알고리즘을 사용해야합니다. 오늘부터 이 세개의 알고리즘을 공부하며 포스팅 할 계획으로, 다익스트라 알고리즘부터 시작하겠습니다. 먼저, 다익스트라 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 거리를 구할 수 있습니다. 단, 간선의 비용은 음수이면 안됩니다. (음수의 간선일 경우 플로이드-와샬 알고리즘을 사용합니다..