# Verifying Shortest Paths in Linear Time

Article · Ahmed Shokry, Amr Elmasry, Ayman Khalafallah, Amr Aly

- Archive id: arxiv:2412.06121
- Published: 2024-12-09
- Venue: International Japan-Africa Conference on Electronics, Communications, and Computations (JAC-ECC)
- DOI: https://doi.org/10.1109/jac-ecc64419.2024.11061218
- arXiv: https://arxiv.org/abs/2412.06121
- Citations: 0
- Source URL: https://arxiv.org/abs/2412.06121
- PDF: https://arxiv.org/pdf/2412.06121
- Provenance: arxiv

## Abstract

In this paper we propose a linear-time certifying algorithm for the single-source shortest-path problem capable of verifying graphs with positive, negative, and zero arc weights. Previously proposed linear-time approaches only work for graphs with positive arc weights.

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

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
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.