On the Dynamic Shortest Path Problem

スポンサーリンク

概要

• 論文の詳細を見る

• This paper proposes an algorithm to solve the dynamic shortest path problem, which is to perform an arbitrary sequence of two kinds of operations on a directed graph with edges of equal length: the insert operation, which inserts an edge into the graph, and the FindShortest operation, which reports the shortest path between a pair of vertices if such a path exists. Each Find Shortest operation can be done in Ο(k) time, where k⩽n is the number of edges on the shortest path, and an arbitrary sequence of at most Ο(n^2) insert operations can be done in a worst-case time of Ο(n^3 1og n). Furtheremore, our algorithm can be extended to perform the cost-decreasing operation of the least-cost path problem, and always takes less time than previous algorithms.

• 一般社団法人情報処理学会の論文
• 1991-02-10

著者

• Lin Chih-chung

  Institute Of Computer And Information Science National Chiao Tung University

• Chang Ruei-chuan

  Institute Of Information Science Academia Sinica

関連論文

• On the Dynamic Shortest Path Problem

スポンサーリンク