Flexsim最短路径算法50行代码搞定Floyd(弗洛伊德)

此算法由Robert W. Floyd(罗伯特·弗洛伊德)于1962年发表在“Communications of the ACM”上。同年Stephen Warshall(史蒂芬·沃舍尔)也独立发表了这个算法。Robert W.Floyd这个牛人是朵奇葩,他原本在芝加哥大学读的文学,但是因为当时美国经济不太景气,找工作比较困难,无奈之下到西屋电气公司当了一名计算机操作员,在IBM650机房值夜班,并由此开始了他的计算机生涯。此外他还和J.W.J. Williams(威廉姆斯)于1964年共同发明了著名的堆排序算法HEAPSORT。堆排序算法我们将在第七章学习。Robert W.Floyd在1978年获得了图灵奖。——引用自【Angel Kitty】博客

本代码同时还参考了【火星十一郎】的博客上写了一篇关于最短路径算法的介绍。废话不多说,按照惯例直接上代码:

var begin = param(1);
var end = param(2);
#define UNREACHABLE 1000000
if (!objectexists(begin) || !objectexists(end))
 return "unreachable";
if (!isclasstype(begin, "AGV::ControlPoint") || !isclasstype(end, "AGV::ControlPoint"))
 return "unreachable";
int n = 0;
Table G = Table(nodeinsertinto(first(model()))); 
Table P = Table(nodeinsertinto(first(model()))); 
Variant vList;
//初始化图
forobjecttreeunder(model())
if(isclasstype(a, "AGV::ControlPoint")) {
 vList.push(a);
 n++;
}
G.setSize(n,n,DATATYPE_NUMBER,UNREACHABLE);
P.setSize(n,n,DATATYPE_NUMBER,UNREACHABLE);
for(int i=1;i<=n;i++) {
 for(int j=1;j<=n;j++) {
  set(G.cell(i,j),cmd_cpdistance(vList[i],vList[j]));
  set(P.cell(i,j),j);
 }
}
//核心
for(int k=1;k<=n;k++) {
 for(int i=1;i<=n;i++) {
  for(int j=1;j<=n;j++) {
   if(get(G.cell(i,j))>get(G.cell(i,k))+get(G.cell(k,j))) {
    set(G.cell(i,j),get(G.cell(i,k))+get(G.cell(k,j)));
    set(P.cell(i,j),get(P.cell(i,k)));
   }
  }
 }
}
//输出
int b = vList.indexOf(begin);
int e = vList.indexOf(end);
int k = 0;
string path = "";
while(b!=e && k>=0) {
 k = get(P.cell(b,e)); 
 if(k> vList.length ||get(G.cell(b,k))>=UNREACHABLE) k=-1;
 else path = path + "-->" + getname(vList[k]);
 b = k;
}
destroyobject(G);
destroyobject(P);
return k<0? "unreachable" : getname(begin)+path;

Floyd算法是一个经典的动态规划算法,可以处理有向图或存在负权边情况的最短路径(这是Djikstra做不到的),该算法时间复杂度为O(N3),空间复杂度为O(N2),矩阵P是获得路径的关键。

Floyd由于时间复杂度较高,建议直接使用的话顶点数不要超过100。另外,如果顶点数很多的话,用它初始化图G、矩阵D、P后,结合其他算法一起用也不失为一种极好的方案。

欢迎留言和交流 。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

1 + 3 =