作业帮图论中求任意两点之间的最短路径用lingo怎么实现,求lingo源程序
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/10/01 22:28:18
图论中求任意两点之间的最短路径用lingo怎么实现,求lingo源程序
请参考：（10个点的最短路径）,源顶点编号为10,
!最短路问题;
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
结果是,
F( 1) 17.00000
F( 2) 11.00000
F( 3) 15.00000
F( 4) 8.000000
F( 5) 13.00000
F( 6) 11.00000
F( 7) 5.000000
F( 8) 7.000000
F( 9) 9.000000
F( 10) 0.000000
!最短路问题;
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
结果是,
F( 1) 17.00000
F( 2) 11.00000
F( 3) 15.00000
F( 4) 8.000000
F( 5) 13.00000
F( 6) 11.00000
F( 7) 5.000000
F( 8) 7.000000
F( 9) 9.000000
F( 10) 0.000000