ON THE QUICKEST PATH PROBLEM

被引：97
|
作者：
CHEN, GH
HUNG, YC
机构：
[1] Department of Computer Science and Information Engineering, National Taiwan University, Taipei
来源：
INFORMATION PROCESSING LETTERS | 1993年 / 46卷 / 03期
关键词：
ANALYSIS OF ALGORITHMS; COMBINATORIAL PROBLEMS; DESIGN OF ALGORITHMS;
D O I：
10.1016/0020-0190(93)90057-G
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Let N be an input network and sigma be the amount of data to be transmitted. We present an O(mn2) time algorithm that finds all-pairs quickest paths, for a given value of sigma, and show that the quickest path between any two nodes for any value of sigma can be found in O(log m) time, provided O(mn2) preprocessing time is spent.
引用
收藏
页码：125 / 128
页数：4
相关论文
共 50 条
12345