The expected length of a shortest path

DOI10.1016/0020-0190(93)90059-IzbMath0784.68064OpenAlexW2074567977MaRDI QIDQ1261487

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

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

Related Items (12)

Distribution of Minimal Path Lengths when Edge Lengths are Independent Heterogeneous Exponential Random Variables ⋮ Unnamed Item ⋮ Solving all-pairs shortest path by single-source computations: theory and practice ⋮ Probabilistic analysis of optimization problems on generalized random shortest path metrics ⋮ Probabilistic analysis of optimization problems on sparse random shortest path metrics ⋮ The computational complexity of avoiding spurious states in state space abstraction ⋮ Learning heuristic functions for large state spaces ⋮ Shortest path network problems with stochastic arc weights ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ Planning and control in artificial intelligence: A unifying perspective ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm ⋮ Typical values of extremal-weight combinatorial structures with independent symmetric weights

Cites Work

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

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