반응형 벨만 포드1 [백준/C++] 타임머신 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 음의 간선이 있기 때문에, Dijikstra알고리즘으로 문제를 풀 수 없다. 음의 사이클이 존재하는지 찾는 알고리즘에는 벨만 포드 알고리즘이 있기 때문에 벨만 포드 알고리즘을 이용해 문제를 풀었다. 벨만 포드 알고리즘에서 음의 사이클이 존재하는지 판단하는 방법은 다음과 같다. N개의 정점이 있을 때, 임의의 정점 A에 도달하기 위해 거쳐야되는 정점의 개수는 총 N-1개다. 그렇기 때문에 음의 사이클이 없다면 임의의 정점에서 다른 정점으로 도달하는 최소비용을 구하는 과정을 N-1번 하면 출발 정점에서 모든 정점에 도달하는 최단경로가 계산이 된다. 이 때, 음의 사이클이 있다면 한번 더 최단경로를 계산했을.. 2024. 4. 18. 이전 1 다음 반응형