2021.07.02
벨만-포드 알고리즘(Bellman-Ford Algorithm)
벨만-포드 알고리즘(Bellman-Ford Algorithm) 음수 가중치가 있는 그래프를 다룰 때 사용하는 알고리즘 그래프의 모든 에지에 대해 다익스트라의 그리디 선택 방법을 (V - 1)번 반복하여 점진적으로 최단 거리를 찾음. V : 정점의 개수 다익스트라 알고리즘보다 높은 점근적 시간 복잡도를 가짐. 다익스트라 알고리즘이 잘못 해석할 수 있는 그래프에 대해서도 정확한 결과를 제공함. 코드 1 음수 가중치 사이클 이 없을 경우 #include #include #include using namespace std; struct Edge { int src; int dst; int weight; }; const int UNKNOWN = INT_MAX; vector BellmanFord(vector edge..
