Bellman Ford 알고리즘의 첫 번째 반복에서 모든 가장자리가 왜 풀리지 않습니까?

Bellman ford 알고리즘은 다음 페이지를 참조하십시오 (예 :). http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm Bellman Ford 알고리즘의 첫 번째 반복에서 모든 가장자리가 왜 풀리지 않습니까?

아직 이해가되지 않습니다. 외부 루프의 첫 번째 루프 반복에서 예를 들어, 먼저 가장자리 1-> 2와 가장자리 1-> 4를 수정한다고 가정 해 봅시다. 가장자리 2-> 3, 2-> 5, 4-> > 3, 4-> 5, 같은 단계에서, 우리는 d [2]와 d [4]를 가지고 있기 때문에. 각 "단계"이제 하나의 정점을 포함하는 방법

set toRelax = {initial_vertex} 
while toRelax is not empty: 
    u = remove a vertex from toRelax 
    for each neighbour v of u: 
     if we can relax u-v: 
      relax u-v 
      add v to toRelax

주의 사항 : 벨만 - 포드의 sligtly 다른 버전을 사용하는 경우

출처

2011-11-21 shahalpk

문제는 없습니다. 그렇게 할 수 있으며 실제로 연결된 코드는이를 수행합니다 (또는 입력 파일에 모서리가 나타나는 순서에 따라 다름). 행복한 결과를 가져 오는 가장자리 완화를 위해 특정 순서를 선택했습니다. 링크 된 포스트에서 모든 에지는 완화 단계를 거칠 때마다 점검되고 각 에지가 완화되면서 거리가 업데이트되므로 첫 번째 이완 반복의 끝에서 모든 에지가 완전히 완화된다는 특정 그래프에 대해 생각할 수 있습니다. –

이 문제는 마술 사라! "동일한 단계"에서 수행되는 작업은 사용중인 특정 구현의 인공물이며 실제로 알고리즘을 변경하지는 않습니다.

출처

2011-11-21 16:44:16 hugomg

나는이 버전을 정말 좋아합니다. 현재 상태를 변경할 기회가있는 가장자리를 완화하려고합니다. 이 접근법에 관한 문헌에 뭔가가 있습니까? 아직도 B-F인가? 반복적 인 Dijkstra의 것 같습니다. 한 단계에서 꼭지점을 최적화하는 대신 미래에 다시 방문 할 수있는 권리를 유지하면서 그 단계에서 얻을 수있는만큼 좋은 결과를 얻을 수 있습니다. –

하지만이 접근법은 부정적인 사이클을 감지하는 능력을 잃어 버렸습니다. http://stackoverflow.com/questions/29817131/bellman-ford-queue-based-approach-from-sedgewick-and-wayne-algorithms-4th-edi?rq=1 –

Bellman Ford 알고리즘의 첫 번째 반복에서 모든 가장자리가 왜 풀리지 않습니까?

답변

관련 문제