벨만포드
-
[알고리즘/벨만포드] 벨만-포드(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...