벨만포드(Bellman Ford) & SPFA

• 최단 경로
  : 시작점이 1개 일 때, 다른 모든 곳으로 가는 최단 경로 구하기
  : A → B 로 가는 최단 경로는 최대 N-1개의 간선으로 이루어짐 (중요한 성질)
  : 최대 N-2개의 정점을 포함하되, 같은 정점이 존재할 수 없다. (같은 정점이 존재하면 최단 경로가 될 수 없다. 돌아가는 걸 반복하는 셈이니까)

• Bellman Ford 알고리즘
  : dist[i] ,시작점에서 i정점까지 가는 최단 경로
  : 모든 정점에 대해서 모든 간선에 대해 아래를 반복하는 것

  if dist[to] > dist[from] + cost:
      dist[to] = dist[from] + cost

• 시간복잡도
  : O(VE)
  : E $\leq$ V2이기 때문에 O(V3)
  : 느린 알고리즘이지만, 가중치가 음수인 경우에 사용가능하여 간혹 사용

• 음수 사이클
  : 음수 사이클이 존재할 경우 가중치가 계속 변경되기 때문에 값이 -∞가 되며, 최단거리가 존재하지 않게 된다.

• SPFA
  : 벨만포드 알고리즘을 빠르게 개량한 것
  : 한 단계에서 to에 대한 거리값이 바꾸지 않으면 to가 from으로 바뀌어도 값이 바뀌지 않는다.
  : queue를 이용해서 변경된 to만 queue에 넣어주고 값 갱신
  : 다익스트라가 제일 빠르기 때문에 잘 사용하지 않는다.
  : 벨만포드 사용할 때 처럼 음의 가중치가 있을 경우에만 주로 사용
  : MCMF알고리즘이 대표적인 예

while queue: # queue가 빌때까지 계속 동작하기 때문에 cnt 성립
        _from = queue.popleft()
        check[_from] = False

        for _to, _cost in edge[_from]:
            if dist[_to] > dist[_from] + _cost:
                dist[_to] = dist[_from] + _cost
                if not check[_to]:
                    queue.append(_to)
                    check[_to] = True
                    cnt[_to] += 1 # 한 정점이 n번이상 방문되면 그 정점을 포함하여 어떠한 음수 사이클이 있다는 것을 확인 가능
                    if cnt[_to] >= n:
                        return True