728x90 벨만포드1 [C++] 벨만-포드(Bellman - Ford) 알고리즘 벨만-포드 알고리즘이란? 벨만-포드 알고리즘은 가중치 방량 그래프에서 최단 경로 문제를 푸는 알고리즘입니다. 다익스트라 알고리즘에서 간선의 가중치가 음수일 수 없었던 것에 반해 벨만-포드 알고리즘은 가중치를 음수 값으로 갖는 것이 가능합니다. 다만 속도 측면에서 다익스트라 알고리즘이 벨만-포트 알고리즘에 비해 빠른 속도를 갖습니다. 과정은 어떤 한 정점에서 어떤 다른 정점으로 갈 때 그 정점의 개수가 N개면 최대 N-1개의 간선을 사용해야 합니다. 그렇게 시장 정점에서 각 정점까지 가는 가는 최소 가중치합을 간선의 선택개수를 N - 1개까지 증가시키며 비교해주면 됩니다. 그렇게 최소 값들을 유지시키면 됩니다. 마지막으로 N - 1 번째 시행했을 때 남은 값들을 출력합니다. 예시 코드 #include #i.. 2021. 8. 26. 이전 1 다음 728x90
