ConstrainedShortestPaths.jl

Overview

This package implements algorithms for solving (resource) Constrained Shortest Paths problems. It implements a generalized A star algorithm with label dominance and optional bounding. It is currently restricted to acyclic directed graphs. Reference: https://arxiv.org/abs/1504.07880.

Let $D=(V, A)$ an acyclic directed graph, $o, d\in V$ origin and destination vertices, $c$ a cost function, and $\mathcal{P} \subset \mathcal{P}_{od}$ a subset of $o-d$ paths in $G$. This package can compute the corresponding constrained shortest path:

$$ \boxed{\begin{aligned} P^\star = \arg\min\quad & c(P)\\ \text{s.t.}\quad & P\in \mathcal{P} \end{aligned}} $$

See the documentation for more details.

Installation

To install this package, open a julia REPL and run the following command:

]add ConstrainedShortestPaths