최단 경로 알고리즘 - Bellman Ford

Bellman Ford

• 시작점에서 다른 모든 정점까지 최단 경로
• 간선 가중치가 음수 가능
• 간선을 List에 담아 N-1 번 모든 간선의 최단 경로 갱신
• N번째에도 최단 경로가 갱신된다면 사이클 존재
• O(VE)

  for(int i=1; i<=N; i++) {
            for(Edge e : list) {
                if(D[e.from]!= INF && D[e.to]> D[e.from]+e.cost) {
                    D[e.to] = D[e.from]+ e.cost;
                    if(i == N)
                        cycleFlag = true;
                }
            }
        }