|
1 /* SPP, Shortest Path Problem */ |
|
2 |
|
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
|
4 |
|
5 /* Given a directed graph G = (V,E), its edge lengths c(i,j) for all |
|
6 (i,j) in E, and two nodes s, t in V, the Shortest Path Problem (SPP) |
|
7 is to find a directed path from s to t whose length is minimal. */ |
|
8 |
|
9 param n, integer, > 0; |
|
10 /* number of nodes */ |
|
11 |
|
12 set E, within {i in 1..n, j in 1..n}; |
|
13 /* set of edges */ |
|
14 |
|
15 param c{(i,j) in E}; |
|
16 /* c[i,j] is length of edge (i,j); note that edge lengths are allowed |
|
17 to be of any sign (positive, negative, or zero) */ |
|
18 |
|
19 param s, in {1..n}; |
|
20 /* source node */ |
|
21 |
|
22 param t, in {1..n}; |
|
23 /* target node */ |
|
24 |
|
25 var x{(i,j) in E}, >= 0; |
|
26 /* x[i,j] = 1 means that edge (i,j) belong to shortest path; |
|
27 x[i,j] = 0 means that edge (i,j) does not belong to shortest path; |
|
28 note that variables x[i,j] are binary, however, there is no need to |
|
29 declare them so due to the totally unimodular constraint matrix */ |
|
30 |
|
31 s.t. r{i in 1..n}: sum{(j,i) in E} x[j,i] + (if i = s then 1) = |
|
32 sum{(i,j) in E} x[i,j] + (if i = t then 1); |
|
33 /* conservation conditions for unity flow from s to t; every feasible |
|
34 solution is a path from s to t */ |
|
35 |
|
36 minimize Z: sum{(i,j) in E} c[i,j] * x[i,j]; |
|
37 /* objective function is the path length to be minimized */ |
|
38 |
|
39 data; |
|
40 |
|
41 /* Optimal solution is 20 that corresponds to the following shortest |
|
42 path: s = 1 -> 2 -> 4 -> 8 -> 6 = t */ |
|
43 |
|
44 param n := 8; |
|
45 |
|
46 param s := 1; |
|
47 |
|
48 param t := 6; |
|
49 |
|
50 param : E : c := |
|
51 1 2 1 |
|
52 1 4 8 |
|
53 1 7 6 |
|
54 2 4 2 |
|
55 3 2 14 |
|
56 3 4 10 |
|
57 3 5 6 |
|
58 3 6 19 |
|
59 4 5 8 |
|
60 4 8 13 |
|
61 5 8 12 |
|
62 6 5 7 |
|
63 7 4 5 |
|
64 8 6 4 |
|
65 8 7 10; |
|
66 |
|
67 end; |