有點對之間最快路問題

頁數(shù) 15 字數(shù) 5456

摘要：所有點對之間最快路問題就是要在所有點對（ ， ）之間傳遞數(shù)據(jù) ，并找出一條最快的路線。解決所有點對之間最快路問題的關(guān)鍵是產(chǎn)生有，效解的等價集合。運用最短路的算法，我們首先涉及了一個時間復(fù)雜度為Ｏ（ ）的產(chǎn)生有效解等價集的算法，然后研究了靜態(tài)點對之間最快路問題和動態(tài)點對之間最快路問題，其算法的時間復(fù)雜度分別為 Ｏ（ ）和Ｏ（ ）。最后本文研究了求和對最小比率路問題，證明該問題可以在Ｏ（ ）時間內(nèi)解決。

關(guān)鍵詞 ：最快路,等價集合,比率路,事件復(fù)雜度。

參考文獻
：
Golden B, Magnanti T. Deterministic network optimization: a bibliography[J],networks,1997,7:149-183.
(2) Deo N Pang Can,shortest path algorithms: taxonomy anb annotation [J].networks,1984,14:273-323
(3) Ibaraki T. algorithms for obtaining shortest paths visiting specified nodes [J].SIAM review,1973,15:309-317.
(4)Cai Xiaoqiang, Kloks T,Wong C K. Time-varying shortest paths
Problem with [J], networks,1997,29:141-149.
(5)Loachin I,Gelinas S. A dynamic programming algorithms for the shortest paths Problemwith time windows and linears node cost [J]. networks,,1998,31:193-204.