# Shortest Paths Avoiding Forbidden Subpaths

Preprint · Mustaq Ahmed, Anna Lubiw

- Archive id: arxiv:0807.0807
- Published: 2008-07-04
- Venue: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS), Freiburg, Germany, 2009, pp. 63-74
- arXiv: https://arxiv.org/abs/0807.0807
- Citations: 0
- Source URL: https://arxiv.org/abs/0807.0807
- PDF: https://arxiv.org/pdf/0807.0807
- Provenance: arxiv

## Abstract

In this paper we study a variant of the shortest path problem in graphs: given a weighted graph G and vertices s and t, and given a set X of forbidden paths in G, find a shortest s-t path P such that no path in X is a subpath of P. Path P is allowed to repeat vertices and edges. We call each path in X an exception, and our desired path a shortest exception-avoiding path. We formulate a new version of the problem where the algorithm has no a priori knowledge of X, and finds out about an exception x in X only when a path containing x fails. This situation arises in computing shortest paths in optical networks. We give an algorithm that finds a shortest exception avoiding path in time polynomial in \|G\| and \|X\|. The main idea is to run Dijkstra's algorithm incrementally after replicating vertices when an exception is discovered.

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