Shortest and Widest Paths

Download notebookThe same code as on this page, ready to run in Jupyter with IJulia.

This example computes all-pairs shortest paths and widest paths on a small directed graph, and then answers single-source and single-target queries from one factorization.

using PATHPACK, SparseArrays, LinearAlgebra
using PATHPACK.CPU: MinPlus, MaxMin, mstar, mlu

The entry A[i, j] is the weight of the arc i → j.

A = sparse([1, 1, 2, 3, 4, 4], [2, 3, 4, 2, 1, 5], [3.0, 8.0, 1.0, 4.0, 2.0, 7.0], 5, 5)

5×5 SparseMatrixCSC{Float64, Int64} with 6 stored entries:
  ⋅   3.0  8.0   ⋅    ⋅ 
  ⋅    ⋅    ⋅   1.0   ⋅ 
  ⋅   4.0   ⋅    ⋅    ⋅ 
 2.0   ⋅    ⋅    ⋅   7.0
  ⋅    ⋅    ⋅    ⋅    ⋅

All Pairs

In the min-plus semiring the star A* holds the distances: A*[i, j] is the length of a shortest path from i to j, and Inf means that j cannot be reached from i.

D = mstar(MinPlus(), A)

5×5 Matrix{Float64}:
  0.0   3.0   8.0   4.0  11.0
  3.0   0.0  11.0   1.0   8.0
  7.0   4.0   0.0   5.0  12.0
  2.0   5.0  10.0   0.0   7.0
 Inf   Inf   Inf   Inf    0.0

In the max-min semiring the same call gives the capacity of the widest path between every pair of vertices.

W = mstar(MaxMin(), A)

5×5 Matrix{Float64}:
  Inf     4.0    8.0    1.0   1.0
   1.0   Inf     1.0    1.0   1.0
   1.0    4.0   Inf     1.0   1.0
   2.0    2.0    2.0   Inf    7.0
 -Inf   -Inf   -Inf   -Inf   Inf

mstar(MinPlus(), A) shortest distance

mstar(MaxMin(), A) widest capacity

Row i, column j: from vertex i to vertex j. Inf: no path; in max-min the diagonal is the semiring's one, Inf.

Queries

A factorization answers queries without forming the whole star. lmul!(F, b) overwrites b with A* b; with the unit vector at vertex 5 (0 there, the semiring's one, and Inf, its zero, elsewhere), that is column 5 of A*: the distances to vertex 5.

F = mlu(MinPlus(), A)
b = fill(Inf, 5); b[5] = 0.0
lmul!(F, b)

5-element Vector{Float64}:
 11.0
  8.0
 12.0
  7.0
  0.0

rmul!(B, F) overwrites the rows of B with B A*; with the unit row vector at vertex 1, that is row 1 of A*: the distances from vertex 1.

B = fill(Inf, 1, 5); B[1] = 0.0
rmul!(B, F)

1×5 Matrix{Float64}:
 0.0  3.0  8.0  4.0  11.0

Both agree with the star.

b == D[:, 5] && vec(B) == D[1, :]

true