최단 경로 찾기 (Bellman-Ford)

벨만 포드 알고리즘

• 음수 비용인 경우도 가능
• 음의 사이클 존재 여부 확인

정점의 개수가 V이면 간선을 V-1개만 사용하면 최단 거리를 만들 수 있다.
O(EV) = O((V-1)V)

1. 시작점에서 다른 정점까지 거리를 무한대로 초기화
2. 모든 간선에 대해
3. 간선의 시작점이 아직 무한대인 경우 패스
4. 간선의 시작점이 무한대가 아닌 경우 도착점 값을 이전 도착점 값과 비교하여 작은 경우 업데이트
5. V-1 회만큼 2~4번을 반복

음의 사이클 찾기

6. V-1회 이후 한번 더 수행했을 때 값이 업데이트가 되는 경우가 있다면
   음의 사이클이 있다.

int dist[V];
ArrayList<Node> adjList = new ArrayList<>();

class Node {
    int start;
    int end;
    int cost;
}

static void bellman(int V) {
    Arrays.fill(dist, INF);
    
    // V-1 번만큼 반복
    for(int v=1; v<=V-1; v++) {
    	for(Node node : adjList) {
            if(dist[node.start] == INF) continue;
            if(dist[node.end] > dist[node.start] + node.cost) {
            	dist[node.end] = dist[node.start] + node.cost;
            }
        }
    }
    
    //음의 사이클 확인
    boolean isNegativeCycle = false;
    for(Node node : adjList) {
    	if(dist[node.start] == INF) continue;
        if(dist[node.end] > dist[node.start] + node.cost) {
            isNegativeCycle = true;
            break;
        }
    }
}