두 노드 사이의 경로를 결정할 때 부정적인 사이클이 없음

Question

그래프의 두 노드 사이의 최단 경로를 결정하려면 왜 가중치가 적용된 가중치 그래프에 음수 사이클이 포함될 수 없습니까?

Answer 1

음 사이클이 다음의 경로 가중치에 영향을 미칠 것이기 때문 웨이 :

a----------b-----------c---------------d 
    2  |  2  |  4 
      |   | 
      | -3  | -3 
      |   | 
      e-----------f 
       2 

경로를 찾는

첫 번째 시도 :

a->b->c->d cost = 8 

이제

의 루프 입력 할 수 :

0123을

그럼 그 두 가지에 의해 저렴하지만, 우리는 더 나은 작업을 수행 할 수 있습니다

a->b->c->(f->e->b->c)^i->d cost = 8 + (-2)^i 

명백한 문제 : 모든 루프를 통해 실행과 경로가 저렴 얻고 우리가 가장 짧은 경로로 무한 루프에 바람.

그러나 이것은 모든 경로 찾기 알고리즘에는 적용되지 않습니다. 예를 들어, Bellman-Ford-algorithm은 덜 효율적인 비용으로 네가티브 엣지를 처리 ​​할 수 ​​있습니다.

Answer 2

이러한주기가 있다면, 생각할 수있는 모든 "최단 경로"에 대해이 부정적인주기를 다시 한번 통과시켜 더 나은 경로를 선택할 수 있습니다. 그리고 이것은 전체 경로 비용을 확실히 감소시킬 것입니다. 왜냐하면 이러한 가정이이주기가 음의 가중치이기 때문입니다.

Answer 3

"최단"은 실제로 "최소 비용/중량"경로를 의미하기 때문에.

음의 가중치주기를 사용하면이 경로를 포함하여 (이주기가 포함 된) 임의의 낮음 가중치를 얻을 수 있습니다.

Answer 4

이렇게하면 최단 경로는 -inf이 될 수 있습니다.

이 예제를 가정 해보면 A와 D 사이의 최단 경로를 계산하고 싶을 것입니다. 아마도 A - B - D가 6 단계가되기를 원할 것입니다. 그러나 사이클 B - C - B를 원하는만큼 반복 할 수 있습니다. B - - C - B - C - ... - 다음으로, 최단 경로 A는 B - C - B - D.