This thesis presents a direct decomposition method for finding K shortest paths in an acyclic network based on a sher's algebra [1]. In this method, unlike the iterative methods of shier [1,2], triangularity of an acyclic network is utilized, in the sense that it implements recursively only the non-trivial operations. The computational complexity to obtain the K shortest paths from node s to all other nodes (or from all the nodes to node s) is O($Ks^2$). Graph-theoretic interpretation and a method of recording paths are also included.
본 논문에서는 비순환 네트웍에서 정해진 K개의 최단 경로를 찾는 효율적인 방법으로서 직접 분할 기법을 제시하고 있다.
비순환 네트웍의 마디간 길이를 나타내는 행렬은 마디들의 번호 조정을 통해 삼각행렬로 만들 수 있는데 이 삼각행렬의 특성을 이용한 것이 직접 분할기법이다. 여기에서는 Shier의 축자적인 방법과는 달리 필요없는 계산을 제거할 수 있고 row나 colum을 하나씩 컴퓨터의 주기억 장소에 기억시켜서 기억장소의 크기를 줄일 수 있기 때문에 매우 효율적이다. 계산량은 $KS^2$에 비례하며 기억 장소의 크기는 $Kn^2$에 비례한다.
직접 분할기법과 동적계획법 사이의 관계를 밝힘으로서 경로상의 마디를 기억시키는 효율적인 방법도 함께 제시하고 있다.
