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