最短路算法应用举例
model:sets:
!节点集合;
nodes/1..10/;
!w邻接矩阵,d(i,j)是节点i到j的最优路长,c(i,j)是节点i到j的最小运费;
link(nodes,nodes):w,d,c;
!u表示迭代过程的权矩阵;
nn(nodes,nodes,nodes):u;
endsets
data:
big=20000;
!w邻接矩阵;
w= 0 11 4 9 9 10 9 8 11 16
11 0 11 18 7 8 8 12 2 11
4 11 0 8 11 17 2 11 9 12
9 18 8 0 6 10 12 5 6 5
9 7 11 6 0 4 2 1 7 6
10 8 17 10 4 0 4 10 4 4
9 8 2 12 2 4 0 15 8 5
8 12 11 5 1 10 15 0 12 9
11 2 9 6 7 4 8 12 0 8
16 11 12 5 6 4 5 9 8 0;
enddata
!以下三个循环语句就是最短路计算公式（floyd-warshall）算法;
!k=1的初值;
@for(nn(i,j,k)|k #eq# 1:u(i,j,k)=w(i,j));
!迭代过程;
@for(nodes(k)|k #lt# @size(nodes):@for(link(i,j):u(i,j,k+1)=
@if(u(i,j,k) #le# u(i,k,k)+u(k,j,k),u(i,j,k),u(i,k,k)+u(k,j,k))));
!最后一迭代得到d;
@for(nn(i,j,k)|k #eq# @size(nodes):d(i,j)=
@if(u(i,j,k) #le# u(i,k,k)+u(k,j,k),u(i,j,k),u(i,k,k)+u(k,j,k)));
!根据最短路d计算运费c;
@for(link:c=d*2);
end dingyixiakankan 迭代过程是什么意思啊？？ LZ能不能告诉我这个代码的中文含义是什么吗？？是哪种类型的题目？ 还是先顶个ing！！！
下了在说！！！ 很难的资料 本帖最后由 shengshengchina 于 2011-10-3 21:17 编辑
好像换一个数据w的话，出现问题！比如：
model:
sets:
!节点集合;
nodes/1..6/;
!w邻接矩阵,d(i,j)是节点i到j的最优路长,c(i,j)是节点i到j的最小运费;
link(nodes,nodes):w,d,c;
!u表示迭代过程的权矩阵;
nn(nodes,nodes,nodes):u;
endsets
data:
big=20000;
!w邻接矩阵;
w= 0 3 1 0 8 0
3 0 2 5 0 7
1 2 0 4 0 3
0 5 4 0 6 1
8 0 0 6 0 2
0 7 3 1 2 0;
@text()=@table(d);
enddata
!以下三个循环语句就是最短路计算公式（floyd-warshall）算法;
!k=1的初值;
@for(nn(i,j,k)|k #eq# 1:u(i,j,k)=w(i,j));
!迭代过程;
@for(nodes(k)|k #lt# @size(nodes): @for(link(i,j):u(i,j,k+1)=
@if(u(i,j,k) #le# u(i,k,k)+u(k,j,k),u(i,j,k),u(i,k,k)+u(k,j,k))));
!最后一迭代得到d;
@for(nn(i,j,k)|k #eq# @size(nodes):d(i,j)=
@if(u(i,j,k) #le# u(i,k,k)+u(k,j,k),u(i,j,k),u(i,k,k)+u(k,j,k)));
!根据最短路d计算运费c;
@for(link:c=d*2);
end
结果所求的距离矩阵d为：
1 2 3 4 5 6
1 0 1 1 0 1 0
2 1 0 0 1 0 1
3 1 0 0 1 0 1
4 0 1 1 0 1 0
5 1 0 0 1 0 1
6 0 1 1 0 1 0
这显然是错的！ shengshengchina 发表于 2011-10-3 21:15 static/image/common/back.gif
好像换一个数据w的话，出现问题！比如：
model:
sets:
感觉好像邻接矩阵设置的有问题，比如说，第一行w=0 3 1 0 8 0 ；应该是想表达1与4，1与6没有直接道路相通，所以设定的时候，应该将其设为一个比较大的数，比如说20000。而不能设为0,设为0代表1与4,1与5重合。
页:
[1]