The expected length of a shortest path

DOI10.1016/0020-0190(93)90059-IMaRDI QIDQ1261487zbMATH OpenOpenAlexFDO

Authors K. Appert

Publication date 27 March 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90059-i

zbMATH Keywords

expected length of shortest pathsgraphs with random arc lengths

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

The object under consideration is a directed complete graph whose arc lengths are independent and exponentially distributed with parameter \(\mu\). For the expected length of a shortest path an easily -- computable summation formula and a closed -- form approximation function are given. Also experimental validation of this result is given.

Recommendations

• Shortest paths in networks with exponentially distributed arc lengths
• The shortest-path problem for graphs with random arc-lengths
• Distribution of minimal path lengths when edge lengths are independent heterogeneous exponential random variables
• On Shortest Paths in Graphs with Random Weights
• The longest minimum-weight path in a complete graph

Cites work

• Distribution of the Time Through a Directed, Acyclic Network
• On Shortest Paths in Graphs with Random Weights
• Shortest paths in networks with exponentially distributed arc lengths
• Shortest Paths in Probabilistic Graphs
• The Stochastic Shortest Route Problem
• The use of cutsets in Monte Carlo analysis of stochastic networks

Cited in

(15)

• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• Shortest path network problems with stochastic arc weights
• Solving all-pairs shortest path by single-source computations: theory and practice
• A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in directed acyclic graphs and reliability
• Distribution of minimal path lengths when edge lengths are independent heterogeneous exponential random variables
• A combinatorial problem on a directed graph
• Shortest path through random points
• Shortest paths in networks with exponentially distributed arc lengths
• Learning heuristic functions for large state spaces
• scientific article; zbMATH DE number 1416161 (Why is no real title available?)
• A forward-backward single-source shortest paths algorithm
• Planning and control in artificial intelligence: A unifying perspective
• Probabilistic analysis of optimization problems on sparse random shortest path metrics
• The computational complexity of avoiding spurious states in state space abstraction
• On the expected length of an orderly path

This page was built for publication: The expected length of a shortest path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1261487)