数学建模社区-数学中国

标题: 最短路算法应用举例 [打印本页]

作者: flystar 时间: 2009-1-16 00:54
标题: 最短路算法应用举例
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

作者: 3052035016 时间: 2009-5-20 14:27
dingyixiakankan

作者: zyq871007 时间: 2009-5-23 21:43
迭代过程是什么意思啊？？

作者: zyq871007 时间: 2009-5-23 21:47
LZ能不能告诉我这个代码的中文含义是什么吗？？是哪种类型的题目？

作者: 好学者 时间: 2010-5-5 11:27
还是先顶个ing！！！
下了在说！！！

作者: qian103nian 时间: 2010-10-17 15:36
很难的资料

作者: shengshengchina 时间: 2011-10-3 21:15
本帖最后由 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
这显然是错的！

作者: hyltt7636 时间: 2012-2-5 01:24

shengshengchina 发表于 2011-10-3 21:15
好像换一个数据w的话，出现问题！比如：
model:
sets:

感觉好像邻接矩阵设置的有问题，比如说，第一行w=0 3 1 0 8 0 ；应该是想表达1与4，1与6没有直接道路相通，所以设定的时候，应该将其设为一个比较大的数，比如说20000。而不能设为0,设为0代表1与4,1与5重合。

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)