有點(diǎn)對(duì)之間最快路問(wèn)題

頁(yè)數(shù) 15 字?jǐn)?shù) 5456

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

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

參考文獻(xiàn)
：
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.