• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

『实践』Matlab实现Flyod求最短距离及存储最优路径

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

Matlab实现Flyod求最短距离及存储最优路径

一、实际数据

  已知图中所有节点的X、Y坐标。

     图中的节点编号:矩阵中的编号

       J01-J62:1-62;

    F01-F60:63-122;

    Z01-Z06:123-128;

    D01-D02:129-130.

 

二、Floyd求所有节点间的最小距离及通过矩阵存储最优路径的节点

 

 

 1 function [ optimal,path,maxnum ] = Floyd( distance,liantong,num,p,q )
 2 %Author:ljy 
 3 %Date:20170919
 4 %弗洛伊德算法求最优路径和记录下最优路径中的节点信息
 5 %distance为节点间的连通距离。通过已知的节点的X、Y坐标和连通矩阵计算而得。其中Inf为不连通节点间的距离。连通节点间的距离为正数(非Inf),连通情况通过连通(liantong)矩阵判断所得。  
 6 %num为所有节点个数
 7 %p和q为不考虑路径的两端节点编号。例如p=[129,129];q=[9,10];表示129到9、129到10的路不连通。
 8 %optimal为最优路径的距离信息
 9 %path为最优路径的路径信息,行和列都为节点编号。path(i,j)为i到j的节点编号。例如:节点1到节点3的最优路径为1-》2-》3,那么path(1,3)=2;path(2,3)=3.
10 %maxnum:最长的最优路径的节点总数 11 %liantong:节点间的连通情况,0为不连通,1为连通。
12 maxnum = 2;
13 
14 
15 %将distance变为邻接矩阵
16 for i = 1:num
17     for j = 1:num
18         if distance(i,j) == 0 & i ~= j
19             distance(i,j) = Inf;
20         end
21     end
22 end
23 
24 %将p与q之间的路径的权重赋值为Inf,即不考虑p与q之间这条路径的最优路径。p、q为0表示没有不考虑的路径
25 for i = 1:size(p)
26     for j = 1:size(q)
27         if p(i) > 0 & q(j) > 0
28             distance(p(i),q(j)) = Inf;
29             distance(q(j),p(i)) = Inf;
30             liantong(p(i),q(j)) = 0;
31             liantong(q(j),p(i)) = 0;
32         end
33     end
34 end
35 
36 %核心算法
37  for k = 1:num
38     for i = 1:num
39         for j = 1:num
40             r = 2;%最优路径所包含的节点个数
41             if distance(i,j) > distance(i,k) + distance(k,j)
42                 distance(i,j) = distance(i,k) + distance(k,j);
43                 %存储最优路径中的节点
44                 p = i;
45                 if liantong(p,j) ~= 0
46                     while liantong(i,j) ~= liantong(p,k) & p ~= k
47                         liantong(p,j) = liantong(p,k);
48                         p = liantong(p,k);
49                         r = r + 1;
50                     end
51                 else
52                     liantong(p,j) = liantong(p,k);
53                     r = r + 1;
54                 end
55             end
56             if r > maxnum
57                 maxnum = r;
58             end
59         end
60     end
61  end
62  
63 %返回数据
64 optimal = distance;
65 path = liantong;
66 end

 

 

 

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
matlab 找到数组中最小值的索引;发布时间:2022-07-18
下一篇:
DelphiActiveXForm的使用实例发布时间:2022-07-18
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap