DAG에 Bellman-Ford 알고리즘이 변경 되었습니까?

Question

Bellman-Ford 알고리즘은 단일 소스 최단 경로 문제를 해결하는 데 유용하며 내 응용 프로그램에 필요한 k 번째 반복에서 모든 꼭지점에 대한 k-hop 최적 성의 독특하고 흥미로운 속성을가집니다. (기본적으로 한 꼭지점 사이에서 최대 k-hop의 최단 경로를 원합니다.)

J. 엔 때문에 Bellman-Ford에 두 개의 wellknown improvements이 있는데, 이는 O (| V |^3) ~ O (| V |^3/4) .. 즉, 1/4에 해당하는 일정한 계수 (각 개선에서 1/2의 계수)로 계산에서 좋은 절약.

그러나 Yen의 방법은 기본적으로 그래프를 두 개의 DAG로 나누고 두 DAG 사이의 반복을 변경하여이 방법을 사용하면 방향성 비순환 그래프 (DAG)에 유용하지 않습니다. 1/2의 이점. 맞습니까?

같은 줄에서, k-hop 최적의 최단 경로를 찾을 수있는 Bellman-Ford에 대한 다른 개선점이나 대안이 있는지 여부를 알 수 있다면 크게 감사하겠습니다.

Answer 1

엔의 수정 내용은 DAG에서 잘 작동합니다. 사실 선형 순서를 DAG의 위상적인 순서로 선택하면 하나의 반복으로 수렴됩니다. 문제는 엔의 수정이 문제를 해결하지 못한다는 것입니다. 왜냐하면 가장자리가 동시에가 아닌 특정 순서로 이완되어야하기 때문입니다. 이것은 대부분의 k 모서리에서 최단 경로를 찾는 데 필요합니다.