그래프 최단 경로 찾기 . 벨만-포드, 다익스트라, 플로이드-워셜 알고리즘
벨만-포드 알고리즘(Bellman-Ford algorithm)은 시작노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 길이(가중치)가 음수인 사이클을 포함하지 않는 모든 그래프를 처리할 수 있다. 또한 길이(가중치)가 음수인 사이클을 포함하는 지도 확인할 수 있다. 시작노드의 거리는 0으로 그리고 나머지 노드까지의 거리는 무한대로 초깃값을 설정하고, 이 값들을 차례로 줄여나가면서 더는 줄일 수 없을때 까지 반복한다. 알고리즘은 n-1번 진행되며, 라운드마다 m개의 간선을 처리하기 때문에 시간복잡도는 O(nm)이다. #include #include #include using namespace std; #define INF 99999999; int main() { // 간선 리스트 (시작노드..
Programming Languages/C++ & Algorithm
2020. 10. 16. 17:39