[week9] 벨만-포드 알고리즘

시작 노드 고정하고 반복 돌면서 최단 거리 갱신

전체 노드 수 - 1 만큼 반복하면서 최단 거리 수정

(전체 노드 수 - 1) 만큼 반복하는 이유

- 노드와 노드 사이의 최대 간선의 수는 최대 (전체 노드 수 - 1) 개임

- 일단 반복을 돌았을 때, 거리가 갱신됐다는 것은 경로에 간선의 개수가 하나 늘었다는 것을 의미

-> 최단 거리의 간선의 수가 전체 노드 수 - 1보다 높으면 음의 사이클을 돌고 있다는 것

- 음의 사이클을 돌면 그냥 그 노드까지이 최단 거리를 구할 수 없음 (무한대로 수렴하기 때문에)

 

 

코드 해석

 

간선 edge가 있을 때

edge.v = 간선의 시작

edge.w = 간선의 목적지

edge.cost = 간선의 가중치

 

dist[x] = 시작점부터 x까지의 거리

 

 

// 전체 노드 수 - 1 만큼 반복
for (int i = 0; i < n - 1; i++) {
      // 간선의 개수만큼 반복
      for (int j = 0; j < m; j++) {
        Edge edge = graph.get(j);
        
        // 목적지까지의 거리가 시작점부터 간선의 시작까지의 거리에 간선의 가중치를 더한것보다 크면, 
        // 이 간선을 포함하는 경로로 갱신
        // 그러면 경로에 포함되는 간선의 길이가 늘어나는 것! 
        // -> 이 경로들의 최댓값이 노드 수 - 1이기 때문에 노드 수 - 1만큼 반복하는 것
        if (dist[edge.v] != Integer.MAX_VALUE && dist[edge.w] > dist[edge.v] + edge.cost) {
          dist[edge.w] = dist[edge.v] + edge.cost;
        }
      }
    }