/* 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;