图论最短路径

（1）matlab作图

G = graph(s, t)

其中，s 和 t 都是节点组成的向量，表示从s 、t对应节点之间有边。

然后，plot(G)即可画出图。

G = graph(s, t, w)

其中，w表示对应边的权重。

例如：

这里用 EdgeLabel 属性把权重设置到边上，设置linewidth 属性为2来改变线宽。

有向图把 graph 改成 digraph 即可。

注意：matlab编号是从1开始连续编号，所以编号时要注意。

（2）Matlab计算最短路径

[P,d] = shortestpath(G,start,end [,‘Method’,‘algorithm’])

其中，

（1）G是一个图（graph对象 | digraph对象）

（2）start是起始节点，end目标节点。

（3）后面是可选参数，一般不用调，默认是auto。可选值：auto、unweighted（无权图）、positive（Dijkstra算法，要求权重非负）、mixed（允许权重为负）。

（4）P是最短路径经过的节点向量

（5）d是最短距离。

例如：

这里把最短路径高亮了。

（3）求任意两点的距离矩阵

d = distances(G [,‘Method’, algorithm])

其中

（1）G是一个图。（graph对象 | digraph对象）

（2）返回值 d 是一个方阵，表示两两之间的最短距离。

（4）找给定范围内所有的点

[nodeIDs, dist] = nearest(G,s,d, [‘Method’, algorithm])

表示返回图 G 中距离 s 节点在d 之内的所有结点及距离。

其中，nodeIDs是结点向量、dist是距离向量。