Bellman-Ford Algorithm   벨만 포드 알고리즘

1. 벨만 포드 알고리즘 (Bellman-Ford Algorithm)

  ㅇ 1958년 Richard Bellman,1962년 Lester Ford가 제안한 알고리즘을 기반으로 함
     - 다익스트라 알고리즘 보다 속도는 느리지만,
     - "음수 가중치 허용" 및 "음수 순환 탐지"라는 제어 능력을 갖추어, 
     - 라우팅 프로토콜(例: RIP의 기반이 되는 거리 벡터 라우팅) 등,
     - 가중치 변동성이 크고 안정적인 예외 처리가 필요한 환경에 적합함 

  ㅇ 특징
     - 간선 가중치가 음수도 처리 가능
     - 순환 포함 허용
        . 결과를 이용하여 음수 가중치 순환을 찾아낼 수 있음
     * 동적 계획법의 기초를 닦은 Richard Bellman의 철학이 반영되어,
        . 큰 문제를 작은 하위 문제(간선의 개수를 하나씩 늘려가며 최단 경로를 갱신하는 과정)로
        . 나누어 해결하는 구조를 띔

  ㅇ 시간복잡도  :  O(nm)  (정점 수 n x 간선 수 m)
     - (n : 정점수, m : 간선수) 
        . 모든 간선을 매 루프 마다 확인하므로, 
        . 다익스트라 알고리즘( O(m log n) 또는 O(m + n log n))에 비해 상대적으로 느림