Direct composition method for K shortest paths in an acylic network

Abstract

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.