最短路径问题的经典算法——Floyd算法（r语言）

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

各位大神，身为一个菜鸟只好发帖求助“最短路径问题的经典算法——Floyd算法”

真的不懂啊，跪求指教

%Floyd算法
%解决最短路径问题，是用来调用的函数头文件
%[D,path]=floyd(a)
%输入参数a是求图的带权邻接矩阵，D(i,j)表示i到j的最短距离,path(i,j)表示i,j之间最短路径上顶点i的后继点
%[D,path,min1,path1]=floyd(a,i,j)
%输入参数a是所求图的带权邻接矩阵，i,j起点终点,min1表示i与j最短距离，path1为最短路径
function[D,path,min1,path1]=floyd(a,start,terminal)
D=a;n=size(D,1);path=zeros(n,n);
for i=1:n
   for j=1:n
      if D(i,j)~=inf
        path(i,j)=j;
      end
   end
end
for k=1:n
   for i=1:n
      for j=1:n
         if D(i,k)+D(k,j)<D(i,j)
           D(i,j)=D(i,k)+D(k,j);
           path(i,j)=path(i,k);
         end
      end
   end
end
if nargin==3
   min1=D(start,terminal);
   m(1)=start;
   i=1;
   path1=[ ];   
   while  path(m(i),terminal)~=terminal
      k=i+1;                              
     m(k)=path(m(i),terminal);
      i=i+1;
   end
   m(i+1)=terminal;
   path1=m;
end

请将这个以matlab语言写成的算法改写为R语言的算法（函数），并调用编写好的函数命令求解如下的V1→V7的最短路径问题：

[em34]拜托拜托

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏1 回帖

关键词：floyd R语言 terminal function Start function start 起点 经典

楼主！！你的帖有人回复吗？你发的这道题是我们运筹学期末上机作业，全班都不会做。。。你如果有答案的话能不能给我发一份，邮箱498597298@qq.com谢谢啦！！！好人一生平安！！！

查看igraph包中下列三个函数的程序脚本即可：
shortest.paths(graph, from, mode=c("all", "out", "in"),algorithm = c("automatic", "unweighted", "dijkstra", "bellman-ford", "johnson"))
get.shortest.paths(graph, from, to=V(graph), output=c("vpath", "epath", both"))
get.all.shortest.paths( )
average.path.length()

Doreen晨 发表于 2015-6-22 19:19
楼主！！你的帖有人回复吗？你发的这道题是我们运筹学期末上机作业，全班都不会做。。。你如果有答案的话能 ...

你们都把运筹和R结合起来用了？

请问你最后做出来了吗？

你们最后做出来了吗？可以分享一下吗？

good luck

Doreen晨 发表于 2015-6-22 19:19
楼主！！你的帖有人回复吗？你发的这道题是我们运筹学期末上机作业，全班都不会做。。。你如果有答案的话能 ...

我们期末作业也是这个  你最后做出来了吗？真的不会呀

####定义Floyd函数
floyd<-function(A){
  n<-nrow(A)
  D<-A
  path<-matrix(0,n,n)
  for(i in 1:n){
    for(j in 1:n){
      if(is.finite(D[i,j])==T){path[i,j]=j}
    }
  }
  for(k in 1:n){
    for(i in 1:n){
      for(j in 1:n){
        if(D[i,k]+D[k,j]<D[i,j]){
          D[i,j]=D[i,k]+D[k,j];
          path[i,j]=path[i,k]
        }
      }
    }
  }
  return(list(D=D,path=path))
}
####创建原始距离矩阵b
a<-matrix(0,7,7)
a[1,2]=3;a[1,3]=5;
a[2,3]=1;a[2,4]=5;a[2,5]=8;
a[3,4]=7;a[3,5]=4;a[3,6]=10;
a[4,5]=3;a[4,7]=6;
a[5,6]=1;a[5,7]=2;
a[6,7]=2
b<-a+t(a)
b[b==0]<-Inf

####调用函数求解

floyd(b)
结果如下：

r小白新手 发表于 2015-6-17 23:25
各位大神，身为一个菜鸟只好发帖求助“最短路径问题的经典算法——Floyd算法”
真的不懂啊，跪求指教 ...

以前做过，你参考下<br>
https://mp.weixin.qq.com/s/mU6ZkynJ1jminKnZtzILBg