福鼎网站建设培训,注册一个公司大概要多少钱,sns网站开发,广告推广软件本贴介绍最短路径的计算#xff0c;实现方式为迪杰斯特拉算法#xff1b;对于弗洛伊德算法#xff0c;区别在于计算了所有结点之间的最短路径#xff0c;考虑到MATLAB计算的便捷性#xff0c;计算时只需要反复使用迪杰斯特拉即可#xff0c;暂不介绍弗洛伊德的实现 迪杰斯…本贴介绍最短路径的计算实现方式为迪杰斯特拉算法对于弗洛伊德算法区别在于计算了所有结点之间的最短路径考虑到MATLAB计算的便捷性计算时只需要反复使用迪杰斯特拉即可暂不介绍弗洛伊德的实现 迪杰斯特拉算法的思想通俗的归纳来说就是从当前结点出发寻找一个未与当前简历连接——且路径最小的点作为下一个寻找到的地址。有关结点是否建立连接需要一个如下的矩阵来辅助记录。 若还未建立连接则将前驱标记为-1距离记录为无穷~
至于Distance内存放的是起点到当前结点的最短距离这一距离可能会不断更新直到寻找到最短的路径为止~ 实现的具体底代码 第一种 [P,d] shortestpath(G, 9, 4) 如上代码中P表示的9与4节点之间最短路径经过的结点而d保存的是最短路径值的总和~ 第二种 D distances(G);
D(1,2);
D(9,4); 如上代码中D是一个存储了任意两结点之间最短路径的矩阵通过索引访问的方式即可求出任意两点的最短路径~ 此外如下是计算求出指定节点指定距离内部的全部结点的实现方式
[nodeIDs,dist] nearest(G, 2, 10); 注意上述几个函数从2017a版本后才能全部使用
如下是创建图并计算图的具体实现方式
s [9 9 1 1 2 2 2 7 7 6 6 5 5 4];
t [1 7 7 2 8 3 5 8 6 8 5 3 4 3];
w [4 8 3 8 2 7 4 1 6 6 2 14 10 9];
G graph(s,t,w);
plot(G, EdgeLabel, G.Edges.Weight, linewidth, 2) set( gca, XTick, [], YTick, [] );[P,d] shortestpath(G, 9, 4);myplot plot(G, EdgeLabel, G.Edges.Weight, linewidth, 2);
highlight(myplot, P, EdgeColor, g) ;
结果如下绿色即为最短路径
