The quickest path problem (Q912765)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The quickest path problem |
scientific article |
Statements
The quickest path problem (English)
0 references
1990
0 references
The authors consider the following modification of shortest path problems: let a digraph with n nodes and m arcs be given. For any arc (u,v) we have its lead time l(u,v) and its capacity c(u,v). The transmission time for \(\sigma\) units of data along this arc is defined as \(t(u,v):=l(u,v)+\sigma /c(u,v)\). The quickest path problem asks for a path from the source to the sink along which the sum of transmission times is minimum. For fixed \(\sigma\), the authors state an algorithm of time complexity \(O(m^ 2+mn \log m)\) to solve the quickest path problem. If a quickest path for any arbitrary \(\sigma\) is looked for, then the network can be preprocessed in \(O(m^ 2+mn \log m)\) time such that finding a quickest path requires only O(log m) additional steps.
0 references
shortest path
0 references
digraph
0 references
quickest path
0 references
transmission times
0 references