有点对之间最快路问题.doc
约15页DOC格式手机打开展开
有点对之间最快路问题,页数 15 字数 5456摘要：所就是要在所有点对（ ， ）之间传递数据 ，并找出一条最快的路线。解决所的关键是产生有，效解的等价集合。运用最短路的算法，我们首先涉及了一个时间复杂度为Ｏ（ ）的产生有效解等价集的算法，然后研究了静态点对之间最快路问题和动态点对...
内容介绍
此文档由会员 王亮亮 发布
有点对之间最快路问题
页数 15 字数 5456
摘要：所有点对之间最快路问题就是要在所有点对（ ， ）之间传递数据 ，并找出一条最快的路线。解决所有点对之间最快路问题的关键是产生有，效解的等价集合。运用最短路的算法，我们首先涉及了一个时间复杂度为Ｏ（ ）的产生有效解等价集的算法，然后研究了静态点对之间最快路问题和动态点对之间最快路问题，其算法的时间复杂度分别为 Ｏ（ ）和Ｏ（ ）。最后本文研究了求和对最小比率路问题，证明该问题可以在Ｏ（ ）时间内解决。
关键词 ：最快路,等价集合,比率路,事件复杂度。
参考文献
：
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.
页数 15 字数 5456
摘要：所有点对之间最快路问题就是要在所有点对（ ， ）之间传递数据 ，并找出一条最快的路线。解决所有点对之间最快路问题的关键是产生有，效解的等价集合。运用最短路的算法，我们首先涉及了一个时间复杂度为Ｏ（ ）的产生有效解等价集的算法，然后研究了静态点对之间最快路问题和动态点对之间最快路问题，其算法的时间复杂度分别为 Ｏ（ ）和Ｏ（ ）。最后本文研究了求和对最小比率路问题，证明该问题可以在Ｏ（ ）时间内解决。
关键词 ：最快路,等价集合,比率路,事件复杂度。
参考文献
：
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.
