我使用MiniZinc根据http://www.hakank.org/minizinc中的hakank模型计算最短路径优化的问题>
我将距离矩阵输入到对称矩阵,使得图形是双向的。
int: start = 2; % start node int: end = 1; % end node int: M = 999; % large number array[1..n, 1..n] of 0..M: d = array2d(1..n,1..n, [ M, 11, 8, 3, 8, 10, 2, 4, % 1-X 11, M, 3, 5, 1, 4, 8, 3, % 2-X 8, 3, M, 5, 7, 7, 11, 4, % 3-X 3, 5, 5, M, 9, 3, 10, 15, % 4-X 8, 6, 7, 9, M, 7, 12, 1, % 5-X 10, 4, 7, 3, 7, M, 6, 9, % 6-X 2, 8, 8, 10, 12, 9, M, 14, % 7-X 4, 3, 4, 15, 1, 9, 14, M % 8-X ] ); % objective to minimize var int: total_cost = sum(i in 1..n, j in 1..n where d[i,j] < M) ( d[i,j]*x[i,j] ); array[1..n] of var -1..1: rhs; % indicating start/end nodes array[1..n, 1..n] of var 0..1: x; % the resulting connection matrix array[1..n, 1..n] of var 0..n*n: y; % output node matrix array[1..n] of var 0..1: outFlow; % out flow array array[1..n] of var 0..1: inFlow; % in flow array constraint % set rhs for start/end nodes forall(i in 1..n) ( if i = start then rhs[i] = 1 elseif i = end then rhs[i] = -1 else rhs[i] = 0 endif ) /\ % assert that all x values is >= 0 forall(i in 1..n, j in 1..n where d[i,j] < M) ( x[i,j] >= 0 /\ y[i,j] >= 0 ) /\ % calculate out flow forall(i in 1..n) ( outFlow[i] = sum(j in 1..n where d[i,j] < M) (x[i,j]) ) /\ % calculate in flow forall(j in 1..n) ( inFlow[j] = sum(i in 1..n where d[i,j] < M) (x[i,j]) ) /\ % outflow = inflow forall(i in 1..n) (outFlow[i] - inFlow[i] = rhs[i]) /\ % do not loops forall(i in 1..n) ( x[i,i] = 0 ) /\ % sanity: there can be no connection in x if there is not % connection in d forall(i,j in 1..n) ( if d[i,j] = M then x[i,j] = 0 else true endif ) ; solve minimize total_cost; output [ if i = 1 /\ j = 1 then "total_cost: " ++ show(total_cost) ++ "\n" ++ "inFlow: " ++ show(inFlow) ++ "\n" ++ "outFlow: " ++ show(outFlow) ++ "\n" ++ " 1 2 3 4 5 6 7 8\n" else "" endif ++ if j = 1 then show(i) ++ " : " else "" endif ++ show_int(4,x[i,j]) ++ if j = n then "\n" else " " endif | i in 1..n, j in 1..n ];
解决方案给出一个输出矩阵,该矩阵指示图的哪个边参与解决方案;但是,解决方案是没有方向的。我无法告诉您采用特定解决方案的先后顺序。在上面的示例中,从节点2到节点1的最短路径给出以下解决方案
total_cost: 6 inFlow: [1, 0, 0, 0, 1, 0, 0, 1] outFlow: [0, 1, 0, 0, 1, 0, 0, 1] 1 2 3 4 5 6 7 8 1 : 0 0 0 0 0 0 0 0 2 : 0 0 0 0 1 0 0 0 3 : 0 0 0 0 0 0 0 0 4 : 0 0 0 0 0 0 0 0 5 : 0 0 0 0 0 0 0 1 6 : 0 0 0 0 0 0 0 0 7 : 0 0 0 0 0 0 0 0 8 : 1 0 0 0 0 0 0 0
这表明对边缘进行了8-> 1、2-> 5、5-> 8的处理,但我无法将所有边缘排序为2-> 5、5-> 8和8-> 1 。
我正在考虑找到起始节点所在的索引(此处为2,5)并搜索矩阵,直到x [i,j
0和x [j,k 0,其中inFlow [j] = outFlow [j] = 1,但是它不起作用,因为可能有一个以上的k满足该问题(输出图是无方向的)。我想知道是否有任何想法如何在解决方案中保存边的顺序。谢谢。一种方法是在代表路径的变量上: