最短路径LINGO算法

例7.4最短路问题给定N个点),,2,1(Nipi组成集合}{ip，由集合中任一点ip到另一点jp的距离用ijc表示，如果ip到jp没有弧联结，则规定ijc，又规定)1(0Nicii，指定一个终点Np，要求从ip点出发到Np的最短路线。这里我们用动态规划方法来做。用所在的点ip表示状态，决策集合就是除ip以外的点，选定一个点jp以后，得到效益ijc并转入新状态jp，当状态是Np时，过程停止。显然这是一个不定期多阶段决策过程。定义)(if是由ip点出发至终点Np的最短路程，由最优化原理可得0)(1,,2,1)},({min)(NfNijfcifijj这是一个函数方程，用LINGO可以方便的解决。!最短路问题;model:data:n=10;enddatasets:cities/1..n/:F;!10个城市;roads(cities,cities)/1,21,32,42,52,63,43,53,64,74,85,75,85,96,86,97,108,109,10/:D,P;endsetsdata:D=65369751191875410579;enddataF(n)=0;@for(cities(i)|i#lt#n:F(i)=@min(roads(i,j):D(i,j)+F(j)););!显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i--j，否则就不是。由此，我们就可方便的确定出最短路径;@for(roads(i,j):P(i,j)=@if(F(i)#eq#D(i,j)+F(j),1,0));end