벨만 포드 알고리즘 ( BellmanFord Algorithm )

 ( 강의 출처 : https://www.youtube.com/watch?v=Ppimbaxm8d8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=13&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 )

 : 벨만 포드 알고리즘

     여러 노드가 있을때, 시작점에서 다른 노드로 가는 최소 경로를 구하는 다익스트라 ( DIjkstra ) 알고리즘은
     음수 간선이 포함된 경우 사용할 수 없다.
     특수한 경우에는 동일한 과정으로 값을 도출할 수 있지만,
     음의 간선이 Cycle을 이루고, 그 Cycle을 순환하는 경우 총 합이 음수라면
     그 사이클을 무한히 회전하면 음의 무한의 최단 거리를 가질 수 있게되기 때문이다.

     음수 간선이 있는 경우 안된다는건 알았는데, 진짜 무한히 돌아서 단축하면 될거같긴하니 참 재밌는 이슈다.
     

     최단 경로 문제는 다음과 같이 분류 할 수 있다.
     1. 모든 간선이 양수인 경우 ( 모든게 음수라면 절대값은 같으니 동일하게 할 수 있겠다. )
     2. 음수 간선이 있는 경우
       1) 음수 간선 순환은 없는 경우
       2) 음수 간선 순환이 있는 경우

     벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용가능하다.
     또한 음수 간선 순환을 감지할 수 있다.
     기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘( O((V+E)logV )에 비해 느리다. 
     ( V는 정점 개수, E는 간선 개수 )

     1. 출발 노드 설정.
     2. 최단 거리 테이블 초기화
     3. N-1번 반복
      1) 전체 간선 E개를 하나씩 확인
      2) 각 간선을 거쳐 다른 노드로 가능 비용을 계산하여 최단 거리 테이블 갱신
     만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행.
     이때 최단 거리 테이블이 갱신된다면, 음수 간선 순환 존재판별.

     벨만 포드 알고리즘 VS 다익스트라 알고리즘

     다익스트라
      : 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
      : 음수 간선이 없다면, 최적의 해를 찾을 수 있음.
   
     벨만 포드 알고리즘
      : 매번 모든 간선을 확인
        : 따라서 다익스트라 알고리즘에서의 최적의 해를 항상 포함
      : 다익스트라 알고리즘에 비해서 시간이 오래걸리지만, 음수 간선 순환을 탐지할 수 있음.


 : 구현

     벨만 포드 알고리즘은 다이나믹 프로그래밍의 분류에 속한다.
     매번 저장해놓은 최소 비용을 이용해 새로운 최소비용으로 갱신하기 때문이다.

     위에 언급한 동작 원리로는 사실 조금 감이 안와서
     다른 사람의 글도 찾아보았지만 비슷할 정도의 설명이였다.

     보기 쉽게 다시 옮기면,

     1. 출발 노드 설정.
     2. 최단 거리 테이블 초기화
     3. N-1번 반복
      1) 전체 간선 E개를 하나씩 확인
      2) 각 간선을 거쳐 다른 노드로 가능 비용을 계산하여 최단 거리 테이블 갱신
     만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행.
     이때 최단 거리 테이블이 갱신된다면, 음수 간선 순환 존재판별.

     이 내용과, 

     ( 출처 : https://sorjfkrh5078.tistory.com/30 )
     1. 시작 정점 선택
     2. 모든 간선들을 탐색하면서, 시작 정점에서 다른 정점까지의 거리가 INF가 아니라면 거리를 갱신.
     이 과정을 ( 정점의 수-1 )  번 만큼 진행한다.
     3. 마지막으로 2번을 수행한다.

     이렇게 두가지 내용인데
     두번째 내용이 좀 더 구상이 된다.

     구현을 해보려 했는데 음.. 중간에 다익스트라의 방식을 섞는게 아니라면 이게 되는지 감이 안잡힌다.
     도저히 감이 안잡혀서 결국 다른분의 코드를 참고했다.
     ( https://sorjfkrh5078.tistory.com/30 )

     자료구조는 동일하게 형성했으나, 내가 최소 경로에 대한 이해가 부족했는지
     아예 감을 못 잡았다. 전체적인 과정을 훑고나면 최소 경로에대한 부분부터 다시 봐야겠다.