alpar@1: /* SPP, Shortest Path Problem */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* Given a directed graph G = (V,E), its edge lengths c(i,j) for all
alpar@1:    (i,j) in E, and two nodes s, t in V, the Shortest Path Problem (SPP)
alpar@1:    is to find a directed path from s to t whose length is minimal. */
alpar@1: 
alpar@1: param n, integer, > 0;
alpar@1: /* number of nodes */
alpar@1: 
alpar@1: set E, within {i in 1..n, j in 1..n};
alpar@1: /* set of edges */
alpar@1: 
alpar@1: param c{(i,j) in E};
alpar@1: /* c[i,j] is length of edge (i,j); note that edge lengths are allowed
alpar@1:    to be of any sign (positive, negative, or zero) */
alpar@1: 
alpar@1: param s, in {1..n};
alpar@1: /* source node */
alpar@1: 
alpar@1: param t, in {1..n};
alpar@1: /* target node */
alpar@1: 
alpar@1: var x{(i,j) in E}, >= 0;
alpar@1: /* x[i,j] = 1 means that edge (i,j) belong to shortest path;
alpar@1:    x[i,j] = 0 means that edge (i,j) does not belong to shortest path;
alpar@1:    note that variables x[i,j] are binary, however, there is no need to
alpar@1:    declare them so due to the totally unimodular constraint matrix */
alpar@1: 
alpar@1: s.t. r{i in 1..n}: sum{(j,i) in E} x[j,i] + (if i = s then 1) =
alpar@1:                    sum{(i,j) in E} x[i,j] + (if i = t then 1);
alpar@1: /* conservation conditions for unity flow from s to t; every feasible
alpar@1:    solution is a path from s to t */
alpar@1: 
alpar@1: minimize Z: sum{(i,j) in E} c[i,j] * x[i,j];
alpar@1: /* objective function is the path length to be minimized */
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: /* Optimal solution is 20 that corresponds to the following shortest
alpar@1:    path: s = 1 -> 2 -> 4 -> 8 -> 6 = t */
alpar@1: 
alpar@1: param n := 8;
alpar@1: 
alpar@1: param s := 1;
alpar@1: 
alpar@1: param t := 6;
alpar@1: 
alpar@1: param : E :   c :=
alpar@1:        1 2    1
alpar@1:        1 4    8
alpar@1:        1 7    6
alpar@1:        2 4    2
alpar@1:        3 2   14
alpar@1:        3 4   10
alpar@1:        3 5    6
alpar@1:        3 6   19
alpar@1:        4 5    8
alpar@1:        4 8   13
alpar@1:        5 8   12
alpar@1:        6 5    7
alpar@1:        7 4    5
alpar@1:        8 6    4
alpar@1:        8 7   10;
alpar@1: 
alpar@1: end;