# A nonenumerative algorithm to find the k longest (shortest) paths in a DAG

Preprint · Fatih Kocan

- Archive id: arxiv:1301.0181
- Published: 2013-01-02
- arXiv: https://arxiv.org/abs/1301.0181
- Source URL: https://arxiv.org/abs/1301.0181
- PDF: https://arxiv.org/pdf/1301.0181
- Provenance: arxiv

## Abstract

In this paper, we present a novel and efficient algorithm to find the k longest (shortest) paths between sources and sinks in a directed acyclic graph (DAG). The algorithm does not enumerate paths therefore it is especially useful for very large k values. It is based on the Valued-Sum-of-Product (VSOP) tool, which is an extension of Zero-suppressed Binary Decision Diagrams (ZBDDs). We assessed the performance of this algorithm with a DAG model of a path-intensive combinational circuit, viz. c6288, that has \\sim10^{20} paths. We found that it took about 64 minutes to compute all paths in this DAG along with their lengths.

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