벨만-포드 알고리즘

벨만-포드 알고리즘

📄 설명

벨만-포드 알고리즘은 다익스트라 알고리즘과는 다르게 음수 간선의 존재를 확인할 수 있습니다.
시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측값과 실제 최단 거리 사이의 오차를 반복적으로 줄여나가는 방식으로 동작합니다.

dist[v] <= dist[u] + w(u, v)
→ (u까지의 최단 거리 + u에서 v로 가는 비용)이 v까지의 최단 거리보다 작다면 dist[v]를 갱신합니다.

음수 간선이 없다면 시작점에서 모든 정점으로 가는 최단 거리를 구하는데 V - 1번의 갱신으로 충분합니다.
만약 V번째 갱신을 성공한다면 음수 간선이 존재한다는 것을 알 수 있습니다. 이 때는 최단 거리를 구하는게 무의미하게 됩니다.

---

💡동작 과정

1. 각각의 정점마다 현재까지 발견한 최소 경로를 갱신할 dist 배열을 만듭니다. 여기서는 1번 정점을 시작점으로 정했기 때문에 dist[1] = 0으로 초기화 해주었습니다.
   

2. 1번 정점부터 6번 정점까지 순회하며 모든 간선들에 갱신 작업을 해줍니다. (첫번 째)
   

3. V - 1번 갱신하지 않았더라도 모든 간선의 갱신을 실패 했다면 종료합니다.

위 그래프는 w(2, 3)이 -5로 음수 간선을 가지고 있습니다. 이 그래프로 갱신 작업을 할 경우 원래 3번 정점까지 가는 최소 거리는 w(1, 3)인 4이지만 dist[2] + w(2, 3)을 하면 -3이 되기 때문에 이 값이 최단 거리가 되어버립니다.
이는 갱신작업을 할 때마다 계속 작아지기 때문에 V번째 갱신 작업 때도 갱신이 성공하게 됩니다.

---

⌨️ 코드

static boolean bellmanFord(int src) {
   upper = new long[V + 1];
   Arrays.fill(upper, INF);
   upper[src] = 0;
   for(int iter = 1; iter <= V; ++iter) {
      boolean chk = false;
      for(int here = 1; here <= V; ++here)
         for(int i = 0; i < adj[here].size(); ++i) {
            int there = adj[here].get(i).to;
            int cost = adj[here].get(i).weight;
            if(upper[here] != INF && upper[there] > upper[here] + cost) {
               upper[there] = upper[here] + cost;
               chk = true;
               if(iter == V) return false;
            }
         }
      if(!chk) return true;
   }
   return true;
}