美文网首页
graphshortestpath 寻找最短路径的代码实现

graphshortestpath 寻找最短路径的代码实现

作者: 汪小鱼 | 来源:发表于2021-09-30 07:40 被阅读0次

    一、句柄的相关概念的理解

    句柄的相关概念参照我的另一篇文章:Matlab 句柄相关概念总结

    二、寻径算法的代码实现

    % 路线权的定义
    w = [2 1 8 6 1 7 9 5 1 2 3 9 4 6 3];
    % 邻接矩阵的构造
    DG = sparse([1 1 1 2 2 3 3 4 4 4 5 5 6 6 7],[2 3 4 4 5 4 7 5 6 7 6 8 7 8 8],w,8,8);
    first = input('请输入初始节点:');
    last = input('请输入终止节点:');
    % 有向赋权图的绘制
    h = view(biograph(DG,[],'ShowWeights','on'));
    [dist,path,pred] = graphshortestpath(DG,first,last);
    % 标记路线经过的节点
    set(h.Nodes(path),'Color',[1 0.6 0.6]);
    % 标记路线经过的路径
    edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'),get(h.Nodes(path),'ID'));
    set(edges,'LineColor',[1 0 0]);
    set(edges,'LineWidth',2.0);
    

    %% 关于代码实现的解释
    1、DG = sparse([1 1 1 2 2 3 3 4 4 4 5 5 6 6 7],[2 3 4 4 5 4 7 5 6 7 6 8 7 8 8],w,8,8);
    sparse(i,j,v,m,n) 根据 i、j 和 v 三元组生成稀疏矩阵 S,以便 S(i(k), j(k)) = v(k),将 S 的大小指定为 m×n。图论矩阵必须要用稀疏矩阵。通常需要指定邻接矩阵的维数 ,否则会出现报错。

    运行结果

    关于 sparse 的具体用法以及原理可以参照:稀疏矩阵-百度百科
    DG 是个 8*8 的矩阵,第一行表示节点起点,第二行表示节点终点,w 是权值,因为这样创建的矩阵是一个上三角矩阵,构造的是一个有向图。
    无向图需要这样操作:在 graphshortestpath 函数设置方向,‘Directed’,0,关闭默认的有向图得到的是一个完整的矩阵,节点之间可以相互到达,没有方向。但直接导入邻接矩阵的话,矩阵返回的是一个双向的路径图,选定节点到其他节点分别有两条路径。大家可以尝试去实现看一下效果。关于无向赋权图的代码实现,可以通过h = view(biograph(DG,[],'ShowArrows','off','ShowWeights','on'));关闭 'ShowArrows' 箭头显示。

    2、h = view(biograph(DG,[],'ShowWeights','on'));
    BG = biograph(CM,IDs)这条语句设置节点的序号名称。IDs 可以使一个元胞数组,数组中每个元素表示一个名字,数组长度与 CM 矩阵行列长度一致。IDs 也可以是一个字符数组(此时各个节点的名字长度相同)。IDs 必须是唯一的,不能重复。
    根据 DG 矩阵构建路线图,[ ] 中可以通过输入元胞数组的形式对节点进行命名。
    例如:{'城市1','城市2','城市3','城市4','城市5','城市6','城市7','城市8'}
    'ShowWeights','on'控制指示边缘权重的文本显示。 选择是 “开启” 或 “关闭”(默认)。
    h = view(biograph) 打开一个图窗口并绘制一个由 Biograph 对象表示的图形,在图窗口中返回 Biograph 对象的深层副本的句柄。 更新现有图形时,可以使用返回的句柄以编程方式或从命令行更改对象属性。 关闭图窗口时,句柄不再有效。 原始的 Biograph 对象保持不变。

    3、[dist,path,pred] = graphshortestpath(DG,first,last);
    DG 是稀疏矩阵,first 是起点,last 是终点。
    dist 表示最短距离,path 表示最短距离经过的路径节点,pred 表示从 first 到每个节点的最短路径中,目标节点的先驱,即目标节点的前面一个节点。

    4、set(h.Nodes(path),'Color',[1 0.6 0.6]);
    根据 grapnshortestpath 中返回的 path,对相关节点进行修改操作。例如可以改变颜色。
    [1 0.6 0.6]:matlab 中的颜色可以使用三维向量表示,为[r g b],其中各个元素的取值在 0 到 1 之间,r 为红色,g 为绿色,b 为蓝色,它和我们常用的使用 256 表示的颜色是一一对应的。

    5、edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'),get(h.Nodes(path),'ID'));
    getedgesbynodeid,从英文本意上理解为:按节点 ID 获取边缘,我们不难知道它的用法
    关于代码edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'),get(h.Nodes(path),'ID'));实测与edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));实现效果一致。

    EDGES = getedgesbynodeid(BIOGRAPH,SOURCE_IDS,SINK_IDS) gets the edge
    handles that connect any of the nodes' SOURCE_IDS to any of the nodes'
    SINK_IDS. SOURCE_IDS and SINK_IDS can be either strings, cell strings,
    or empty strings (gets all).
    
    % 获取连接任何节点的source_id到任何节点的sink_id的边缘句柄。
    % source_id和sink_id可以是字符串、单元格字符串或空字符串(获取所有字符串)。
    

    三、set、get的用法总结

    set:设置图形对象属性
    set(H,Name,Value) 为 H 标识的对象指定其 Name属性的值。使用时须用单引号将属性名引起来,例如,set(H,'Color','red')。如果 H 是对象的向量,则 set 会为所有对象设置属性。如果 H 为空(即 []),set 不执行任何操作,但不返回错误或警告。
    set(H,NameArray,ValueArray) 使用元胞数组 NameArrayValueArray指定多个属性值。要为 m 个图形对象中的每个图形对象设置 n 个属性值,请将ValueArray 指定为 m×n 的元胞数组,其中 m = length(H),而 n 等于 NameArray 中包含的属性名的数量。

    get:查询图形对象属性
    v = get(h) 返回 h 标识的图形对象的所有属性和属性值。
    v = get(h,propertyName) 返回特定属性 propertyName 的值。使用时须用单引号将属性名引起来,例如,get(h,'Color')

    最后的实现效果:

    寻径完成

    相关文章

      网友评论

          本文标题:graphshortestpath 寻找最短路径的代码实现

          本文链接:https://www.haomeiwen.com/subject/wvwrnltx.html