/* SPP, Shortest Path Problem */

/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */

/* Given a directed graph G = (V,E), its edge lengths c(i,j) for all
   (i,j) in E, and two nodes s, t in V, the Shortest Path Problem (SPP)
   is to find a directed path from s to t whose length is minimal. */

param n, integer, > 0;
/* number of nodes */

set E, within {i in 1..n, j in 1..n};
/* set of edges */

param c{(i,j) in E};
/* c[i,j] is length of edge (i,j); note that edge lengths are allowed
   to be of any sign (positive, negative, or zero) */

param s, in {1..n};
/* source node */

param t, in {1..n};
/* target node */

var x{(i,j) in E}, >= 0;
/* x[i,j] = 1 means that edge (i,j) belong to shortest path;
   x[i,j] = 0 means that edge (i,j) does not belong to shortest path;
   note that variables x[i,j] are binary, however, there is no need to
   declare them so due to the totally unimodular constraint matrix */

s.t. r{i in 1..n}: sum{(j,i) in E} x[j,i] + (if i = s then 1) =
                   sum{(i,j) in E} x[i,j] + (if i = t then 1);
/* conservation conditions for unity flow from s to t; every feasible
   solution is a path from s to t */

minimize Z: sum{(i,j) in E} c[i,j] * x[i,j];
/* objective function is the path length to be minimized */

data;

/* Optimal solution is 20 that corresponds to the following shortest
   path: s = 1 -> 2 -> 4 -> 8 -> 6 = t */

param n := 8;

param s := 1;

param t := 6;

param : E :   c :=
       1 2    1
       1 4    8
       1 7    6
       2 4    2
       3 2   14
       3 4   10
       3 5    6
       3 6   19
       4 5    8
       4 8   13
       5 8   12
       6 5    7
       7 4    5
       8 6    4
       8 7   10;

end;