最短路径 程序

最短路问题给定 N个点p (i 1, 2, , N) i = L 组成集合{ } i p ，由集合中任 一点i p 到另一点j p 的距离用ij c 表示，如果i p 到j p 没有弧联结，则规定= +¥ ij c ， 又规定c 0(1 i N) ii = £ £ ，指定一个终点N p ，要求从i p 点出发到N p 的最短路线。 这里我们用动态规划方法来做。用所在的点i p 表示状态，决策集合就是除i p 以外的 点，选定一个点j p 以后，得到效益ij c 并转入新状态j p ，当状态是N p 时，过程停 止。显然这是一个不定期多阶段决策过程。 定义 f (i)是由i p 点出发至终点N p 的最短路程，，用LINGO可以方便的解决。 !最短路问题; model: data: n=10; enddata sets: cities/1..n/: F; !10个城市; roads(cities,cities)/ 1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8 5,7 5,8 5,9 6,8 6,9 7,10 8,10 9,10 /: D, P; endsets data: D= 6 5 3 6 9 7 5 11 9 1 8 7 5 4 10 5 7 9; enddata F(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