General network에서 k번째 최단경로를 구하기 위한 효율적 앨고리즘 = An efficient algorithm for the k-th shortest loopless paths between a pair of nodes in a network

다국어 초록 (Multilingual Abstract)

We present two algorithms for finding the k-th shortest loopless paths from one node to another node. The first algorithm can be applied to general networks where some are distances are negatives. The second algorithm can be applied only to networks where all are distances are non-negative. In the best case, the first algorithm requires ?? addition-subtractions and ½kn²comparisons ,and second algorithm requires kn²additions and ½kn² comparisons. In the worst case, the first algorithm requires ⅓kn³addition-subtractions and ⅓kn³ comparisons, and the second algorithm requires ?? additions and ⅓kn³comparisons.