파이썬1 [최단경로 알고리즘 - 3] 벨만 포드 알고리즘 * 벨만 포드 알고리즘이란? 시작 정점으로부터 다른 정점까지의 최단 경로를 찾기 위한 알고리즘이다. 벨만 포드 알고리즘의 특징은 다음과 같다. 1. 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있다. 2. 음수 사이클의 존재 여부를 알 수 있다. 음수 사이클 안에서 무한루프를 도는 경우를 알 수 있는 방법은, 그래프 정점의 개수를 V라고 할 때 인접 간선을 검사하고 거리 값을 갱신하는 과정을 V-1 번으로 제한하면 가능해진다. 그래프의 시작 정점에서 특정 정점까지 도달하기 위해 거쳐 가는 최대 간선 수는 V-1개이기 때문에 V번째 간선이 추가되는 순간 사이클이라고 판단할 수 있게 된다. 벨만 포드 알고리즘의 시간 복잡도는 O(VE)이다. 매번 모든 간선을 전부 확인하기.. 2021. 11. 14. 이전 1 다음
