ON THE QUICKEST PATH PROBLEM

Authors
CHEN GH HUNG YC
Citation
Gh. Chen et Yc. Hung, ON THE QUICKEST PATH PROBLEM, Information processing letters, 46(3), 1993, pp. 125-128
Citations number
10
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
46
Issue
3
Year of publication
1993
Pages
125 - 128
Database
ISI
SICI code
0020-0190(1993)46:3<125:OTQPP>2.0.ZU;2-4
Abstract
Let N be an input network and sigma be the amount of data to be transm itted. We present an O(mn2) time algorithm that finds all-pairs quicke st 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.