コード発生方式を用いた最短径路計算プログラム

概要

論文の詳細を見る
An efficient shortest path calculation methodsuitable for real-time processing is presented. The algorithm used here is the one which has an algebraic analogy with the Crout elimination method for solving linear algebraic equations. By symbolic processing a computer program generates another program which represents the optimal reduced Crout algorithm in the sense that only non-trivial operations required for a given particular network structure areexecuted. Furthermore the generated program inculudes no DO-loop and requires no address calculation. Themethod proposed here, which may be called a shortest path version of the "code generation technique", is particularly powerful when a network of fixed sparseness structure must be solved repeatedly with different numerical values. In example networks, the execution of the generated program was observed to be five-to eight-fold as fast as that of existing shortest path programs.
一般社団法人情報処理学会の論文
1976-11-15