Usual shortest path

In this first tutorial, we will use the basic_shortest_path method to solve the usual shortest path problem (no constraints and linear cost) :

\[\min_{P\in \mathcal{P_{od}}} \sum_{a\in P} c_a\]

Let's import the package, and fix the seed for reproducibility.

using ConstrainedShortestPaths
using Random

Random.seed!(67)
include("utils.jl"); # imports random_acyclic_digraph

We wreate a random acyclic directed graph

nb_vertices = 50
g = random_acyclic_digraph(nb_vertices)

{50, 535} directed simple Int64 graph

The adjacency matrix is triangular

adjacency_matrix(g)

50×50 SparseArrays.SparseMatrixCSC{Int64, Int64} with 535 stored entries:
⎡⠈⠲⣓⢼⡝⠷⡍⢼⠔⠩⣄⠹⡁⣚⠸⡺⠡⢋⠱⠒⡆⡄⡟⣔⢁⎤
⎢⠀⠀⠈⠢⡆⢊⢦⣒⣊⡅⣗⡣⡑⡂⠘⡅⡡⢉⢄⣎⣖⠞⠜⡟⠾⎥
⎢⠀⠀⠀⠀⠈⠺⣸⣅⣈⠒⠂⠄⡠⣕⢏⢰⡋⠮⠘⠂⠌⠈⣑⠒⠊⎥
⎢⠀⠀⠀⠀⠀⠀⠈⠪⡉⣰⢅⡭⠿⠉⡎⠗⣂⠴⡋⣠⡜⢝⠓⠹⡪⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠈⠳⡰⢈⢄⠂⡘⡑⢎⢃⠗⠋⡄⠐⢏⠠⡟⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠪⡩⠸⣎⡮⡉⡠⠀⡠⡉⠤⢑⢒⡳⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠢⣱⡔⠔⣸⢡⠲⣍⡱⢜⠔⠦⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠢⣈⠝⠐⢅⡈⠍⠶⡍⣚⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⡤⡤⢠⢗⡟⣂⣃⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠪⣁⣨⠐⢸⠁⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣊⣕⡐⎥
⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠲⣉⎥
⎣⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⎦

Create a cost matrix with random values

using SparseArrays
distance_list = [rand() * 20 - 5 for _ in 1:ne(g)]
I = [src(e) for e in edges(g)]
J = [dst(e) for e in edges(g)]
cost_matrix = sparse(I, J, distance_list);

Compute the shortest path

p_star, c_star = basic_shortest_path(g, 1, nb_vertices, cost_matrix)
@info "Solution found" c_star p_star'

┌ Info: Solution found
│   c_star = -30.89060568174394
│   p_star' =
│    1×17 adjoint(::Vector{Int64}) with eltype Int64:
└     1  5  6  9  10  11  14  15  23  26  27  36  42  43  47  48  50

We can check that we obtain the same results with the dynamic programming algorithm from Graphs.jl

p = enumerate_paths(bellman_ford_shortest_paths(g, 1, cost_matrix), nb_vertices)
c = sum(cost_matrix[p[i], p[i + 1]] for i in eachindex(p[1:(end - 1)]))
@info "Bellman" c p'

┌ Info: Bellman
│   c = -30.89060568174394
│   p' =
│    1×17 adjoint(::Vector{Int64}) with eltype Int64:
└     1  5  6  9  10  11  14  15  23  26  27  36  42  43  47  48  50

This page was generated using Literate.jl.