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

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

句柄的相关概念参照我的另一篇文章：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) 使用元胞数组 NameArray 和ValueArray指定多个属性值。要为 m 个图形对象中的每个图形对象设置 n 个属性值，请将ValueArray 指定为 m×n 的元胞数组，其中 m = length(H)，而 n 等于 NameArray 中包含的属性名的数量。

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

最后的实现效果：

寻径完成