两个单一节点之间的最短路径

#两个单一节点之间的最短路径| 来源: 网络整理| 查看: 265

打开实时脚本

使用节点之间的距离作为边权重来寻找图中节点之间的最短路径。

创建一个包含 10 个节点的图。

s = [1 1 2 2 3 4 4 4 5 5 6 6 7 8 9]; t = [2 4 3 5 6 5 7 9 6 7 7 8 9 10 10]; G = graph(s,t);

为图节点创建 x 和 y 坐标。然后通过指定 'XData' 和 'YData' 名称-值对组，使用节点坐标绘制图。

x = [1 2 3 2 2.5 4 3 5 3 5]; y = [1 3 4 -1 2 3.5 1 3 0 1.5]; plot(G,'XData',x,'YData',y)

通过计算图节点之间的欧几里德距离，为图添加边权重。根据节点坐标 (xi,yi) 计算距离，如下所示：

d=|Δx|2+|Δy|2=|xs-xt|2+|ys-yt|2.

要计算 Δx 和 Δy，首先使用 findedges 获得说明图中每条边的源节点和目标节点的向量 sn 和 tn。然后使用 sn 和 tn 对 x 和 y 坐标向量进行索引，并计算 Δx=xs-xt 和 Δy=ys-yt。hypot 函数计算平方和的平方根，因此指定 Δx 和 Δy 作为输入参数来计算每条边的长度。

[sn,tn] = findedge(G); dx = x(sn) - x(tn); dy = y(sn) - y(tn); D = hypot(dx,dy);

将距离作为边权重添加到图中，并用带标签的边来重新绘制图。

G.Edges.Weight = D'; p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);

计算节点 1 和节点 10 之间的最短路径，并指定两个输出来同时返回路径长度。对于加权图，shortestpath 自动使用考虑边权重的 'positive' 方法。

[path,len] = shortestpath(G,1,10)path = 1×4 1 4 9 10 len = 6.1503

使用 highlight 函数显示图中的路径。

highlight(p,path,'EdgeColor','r','LineWidth',2)

【本文地址】

公司简介

联系我们