# Shortest path with linear resource constraints

In this tutorial we want to solve the following resource constrained shortest path:

\[\begin{aligned} \min_{p\in \mathcal{P_{od}}} & \sum_{a\in p} c_a & \\ s.t. & \sum_{a\in p} w_a^k \leq W^k, & \forall k \in [K] \end{aligned}\]

```
using ConstrainedShortestPaths
using Graphs, SparseArrays
using GLMakie, GraphMakie
```

Let's create a simple graph:

```
nb_vertices = 4
graph = SimpleDiGraph(nb_vertices)
edge_list = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]
distance_list = [1, 2, -1, 1, 1]
for (i, j) in edge_list
add_edge!(graph, i, j)
end
I = [src(e) for e in edges(graph)]
J = [dst(e) for e in edges(graph)]
d = sparse(I, J, distance_list)
```

```
3×4 SparseArrays.SparseMatrixCSC{Int64, Int64} with 5 stored entries:
⋅ 1 2 ⋅
⋅ ⋅ -1 1
⋅ ⋅ ⋅ 1
```

We now add resource costs $w_a$ on edges, and a resource constraint of the form: $\sum\limits_{a\in P} w_a \leq W$

```
W = [1.0]
cost_list = [[0], [0], [10], [0], [0]]
w = [0.0 for i in 1:nb_vertices, j in 1:nb_vertices, k in 1:1]
for ((i, j), c) in zip(edge_list, cost_list)
w[i, j, :] = c
end
graphplot(
graph;
node_color=:red,
nlabels=["$i" for i in 1:nb_vertices],
elabels=["d=$(d[e.src, e.dst]), w=$(w[e.src, e.dst, :])" for e in edges(graph)],
)
```

With these costs, the optimal path should be [1, 2, 4], with length 2.

```
p_star, c_star = resource_shortest_path(graph, W, d, w)
@info "Solution found" p_star c_star
```

*This page was generated using Literate.jl.*