난 그냥 새로운 알고리즘을 배우기 시작했지만 나는 괴짜를 위해 괴짜에 벨보이 포드 알고리즘을 읽을 때 나는 붙어있어 : -이 http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/Bellman Ford 알고리즘은 임의의 임의의 차수의 에지를 가질 수 있습니까?
그것은 기록
알고리즘은 상향식 최단 경로를 계산 독일인의 . 먼저 은 경로의 한쪽 끝에서 까지의 최단 경로에 대한 최단 거리를 계산합니다. 그런 다음 가장 짧은 경로를 , 최대 2 개 가장자리까지 계산합니다.
외부 루프의 i 번째 반복 후에, 대부분의 i 에지를 갖는 최단 경로가 계산됩니다. 최대 | V |가있을 수 있습니다. - 간단한 경로에서 1 가장자리, 그 이유는 외부 루프 실행 | v | - 1 번. 아이디어는, 부정적인 가중치 순환이 없다고 가정 할 때, 최대 i 개의 에지를 갖는 최단 경로를 계산하면, 모든 에지에 걸친 반복은 at-most (i + 1) 에지를 갖는 최단 경로를 보장합니다.
다음 예제 그래프로 알고리즘을 이해해 보겠습니다. 이 원본에서 이미지를 가져옵니다.
주어진 소스 버텍스를 0으로 설정하십시오. 소스까지의 거리를 제외하고 모든 거리를 무한대로 초기화하십시오. 그래프의 총 정점 수는 5이므로 모든 에지를 4 번 처리해야합니다. 아래의 예에서
경우 에지 BE- (AB)의 순서로 다음 (ED) (DC), (AC), (BC), (DB) (BD), (BE) 하나의 반복 만이 가장 짧은 경로를 계산합니다. 2-3 에지는 "가장 먼저 경로의 한쪽 가장자리 인 이있는 최단 경로에 대해 가장 가까운 거리 인 을 최단 거리로 계산 한 다음 최단 경로를 계산합니다등이 있습니다. 외부 루프의 i 번째 반복 후에는 최대 i 모서리가있는 의 최단 경로가 계산됩니다. "따라서 에지의 순서를 변경하면이 명령문은 거짓으로 판명됩니다.
다음 예제 그래프를 사용하여 알고리즘을 이해해 보겠습니다. 이 원본에서 이미지를 가져옵니다.
주어진 소스 버텍스를 0으로 설정하십시오. 소스까지의 거리를 제외하고 모든 거리를 무한대로 초기화하십시오. 그래프의 총 정점 수는 5이므로 모든 에지를 4 번 처리해야합니다. (D, B), (B, D), (A, B), (A, C), (D (B, E)
모든 에지는 다음과 같은 순서로 처리하자 , C), (B, C), (E, D). 모든 모서리가 처음 처리 될 때 우리는 거리를 따라갑니다. 첫 번째 줄은 초기 거리를 나타냅니다. 두 번째 행은 가장자리 (B, E), (D, B), (B, D) 및 (A, B)가 처리 될 때의 거리를 나타냅니다. 세 번째 행은 (A, C)가 처리 될 때의 거리를 보여줍니다. 네 번째 행은 (D, C), (B, C) 및 (E, D)가 처리되는시기를 나타냅니다. 
첫 번째 반복은 최대 1 에지 길이 인 모든 최단 경로를 제공하도록 보장합니다. 모든 모서리가 두 번째로 처리 될 때 거리에 따라옵니다 (마지막 행은 최종 값을 보여줍니다).
번째 반복 보장 많아야 2 개 에지 긴 최단의 경로를 얻었다. 알고리즘은 모든 에지를 2 번 이상 처리합니다. 거리는 두 번째 반복 후에 최소화되므로 세 번째 및 네 번째 반복은 거리를 업데이트하지 않습니다.
질문의 프레젠테이션이 매우 깨끗하고 자세한 내용이지만 실제 질문이 무엇인지 이해하는 것은 약간 어렵습니다. 또한 위의 첫 번째 노란색 블록에서 가장자리 'BD'와 'DB'가 누락되었다고 생각합니다. – Codor
예, 더 정확하게 어디에 갇혀 있었습니까? :) –
BD 및 DB를 놓친 것을 고맙습니다. 제 질문은 bellman ford의 여러 비디오를 보았고 여러 사이트에서 무작위 순서로 가장자리를 찍을 수 있지만 여기서는 첫 번째 반복에서 최단 경로가 1 등으로 표시된다는 것입니다. 어떤 모서리의 순서가있는 경우에만 올바른 것으로 보입니다. – coderAJ