/*
	Shortest Path Probelem: LP version
	V = 1:6
	source = 1
	terminal = 5
E = (1, 2), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 5), (4, 3), (4, 6), (5, 3), (5, 6), and there inversions
w12 = 1, w13 = 5, w21 = 1, w23 = 4, w24 = 2, w31 = 5, w32 = 4,  w35 = 2, w43 = 3 , w46 = 3, w56 = 4
*/

var x12, >= 0, <= 1;
var x13, >= 0, <= 1;
var x21, >= 0, <= 1;
var x23, >= 0, <= 1;
var x24, >= 0, <= 1;
var x31, >= 0, <= 1;
var x32, >= 0, <= 1;
var x35, >= 0, <= 1;
var x43, >= 0, <= 1;
var x46, >= 0, <= 1;
var x53, >= 0, <= 1;
var x56, >= 0, <= 1;


param w12 := 1 ;
param w13 := 5 ;
param w21 := 1 ;
param w23 := 2 ;
param w24 := 2 ;
param w31 := 5 ;
param w32 := 4 ;
param w35 := 2 ;
param w43 := 3 ;
param w46 := 3 ;
param w53 := 1 ;
param w56 := 4 ;

minimize z: w12*x12 + w13*x13 + w21*x21 + w23*x23 + w24*x24 + w31*x31 + w32*x32 + w35*x35 + w43*x43 + w46*x64 + w53*x53 + w56*x56 ;

s.t. source1: x12 + x13 - (x21 + x31) = 1 ;
s.t. terminal5: x53 + x56 - x35 = -1 ;
s.t. mid2: x21 + x23 + x24 - (x12 + x32) = 0 ;
s.t. mid3: x31 + x32 + x35 - (x13 + x23 + x43 + x53) = 0 ;
s.t. mid4: x43 + x46 - x24 = 0 ;
s.t. mid6: - (x46 + x56) = 0 ;

end ;