中国网库做网站,wordpress 关键词链接,陕西门户网站建设,小学门户网站建设方案Matlab实现Flyod求最短距离及存储最优路径 一、实际数据 已知图中所有节点的X、Y坐标。 图中的节点编号#xff1a;矩阵中的编号 J01-J62:1-62; F01-F60:63-122; Z01-Z06:123-128; D01-D02:129-130. 二、Floyd求所有节点间的最小距离及通过矩阵存储最优路径的节点 1 function …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:201709194 %弗洛伊德算法求最优路径和记录下最优路径中的节点信息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 转载于:https://www.cnblogs.com/landiljy/p/7567167.html
