On the quickest path problem
type: Item
instance of: scholarly article
title: On the quickest path problem
zbMATH Open document ID: 0779.68065
DOI: 10.1016/0020-0190(93)90057-G
author: Gen-Huey Chen
author: Yung-Chen Hung
published in: Information Processing Letters
publication date: 1994-01-19T00:00:00Z
review text: The problem of finding the all-pairs quickest path (between every pair of nodes) in an \(N\) input network is analyzed \((N=(V,A,C,L),| V|=n,| A|=m\) are numbers of nodes and arcs respectively, \(C(u,v)\) and \(L(u,v)\) are capacity and lead time respectively). An algorithm is presented to solve the problem for a given \(\sigma\) (the amount of data being transmitted). It is shown that the quickest path between any 2 nodes for a \(\sigma\) can be found in \(O(\log m)\) time, providing \(O(mn)^ 2\) preprocessing time.
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 404996
zbMATH Keywords: all-pairs quickest path
MaRDI profile type: Publication
cites work: Minimum cost-reliability ratio path problem
cites work: The quickest path problem
cites work: Shortest-path algorithms: Taxonomy and annotation
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: Deterministic network optimization: A bibliography
cites work: Q3885184
cites work: Algorithms for finding paths with multiple constraints
cites work: Bibliography on Algorithms for Shortest Path, Shortest Spanning Tree, and Related Circuit Routing Problems (1956–1974)
full work available at URL: 0020-0190(93)90057-g
OpenAlex ID: W2019129092
description: scientific article; zbMATH DE number 404996