# A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates

Preprint · Eyal Weiss, Ariel Felner, Gal A. Kaminka

- Archive id: arxiv:2208.11489
- Published: 2022-08-22
- DOI: https://doi.org/10.3233/faia230567
- arXiv: https://arxiv.org/abs/2208.11489
- Source URL: https://arxiv.org/abs/2208.11489
- PDF: https://arxiv.org/pdf/2208.11489
- Provenance: arxiv

## Abstract

The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. This raises several generalized variants of the shortest path problem. We introduce the problem of finding a path with the tightest lower-bound on the optimal cost. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.