포지티브 가중치 지정 비 주기적 그래프의 k- 에지 최단 경로

Question

포지티브 가중치 지정 및 비순환 그래프 인 G = (V, E)가 표시됩니다. s에서 t까지의 k-edge 최단 경로를보고하기 위해 O (k (m + n))에서 실행되는 알고리즘을 설계하려고합니다. k- 에지 최단 경로는 k 개의 에지를 갖는 s에서 t까지의 경로로서 정의되며, 경로의 총중량은 s에서 t까지의 모든 경로에 대해 최소가되어야한다.

BFS는 가중치가 같지 않은 한 최단 경로를 찾기 위해 단독으로 사용할 수 없기 때문에 BFS를 사용하여 k 에지가있는 경로를 찾는 것이 실행 시간이라고 생각합니다. 저를 버리는 것은 k입니다. BFS k 번 수행을 의미한다고 생각합니다.

내 생각에 모든 가능한 k- 링크 경로를 찾기 위해 소스에서 BFS를 실행하는 것이 좋습니다. 길을 따라 레벨을 추적하고 큐에 추가 할 때 각 노드에 총 경로 가중치를 저장하면 모든 가능한 k- 링크 경로와 해당 가중치를 찾을 수 있습니다. 분명히, 더 낮은 경로 가중치로 낮은 레벨에서 대상을 만난다면, 정의 상 k 에지 최단 경로가 없습니다. 총 무게가 적은 k 개 이상의 모서리가있는 경로가있는 경우는 어떻게됩니까? 또한 O (k (m + n))가 아닙니다. 유용한 힌트를 주시면 감사하겠습니다.

Answer 1

하자 처음에 우리가 f[i][]를 사용하는 각 라운드

하여 수행 할 수 있습니다 f[i + 1][]을 계산하기 위해, 그리고 K - 1 번 반복

f[1][x] = e(s, x); 

이, s에서 j에 내가 링크 최단 경로가 될 f[i][j]

for each node v: 
    f[i + 1][v] = INF; 
for each edge e[u][v]: 
    f[i + 1][v] = min(f[i + 1][v], f[i][u] + e[u][v]); 

은 O(k(n + m))입니다.