温馨提示：本文一共5339字，阅读并理解全文大概需要15分钟左右

图论最短路径问题

本讲将简要介绍图论中的基本概念，并主要讲解图论中的最短路径问题。根据图的不同，我们将学习两种不同的算法：
迪杰斯特拉Dijkstra算法和Bellman‐Ford（贝尔曼‐福特）算法

学过离散数学的同学应该对图都不陌生。
图论中的图（Graph）是由若干给定的点及连接两点的线
所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
一个图可以用数学语言描述为G(V(G),E(G))。V(vertex)指的是图的顶点集，E(edge)指的是图的边集。
根据边是否有方向，可将图分为有向图和无向图。
另外，有些图的边上还可能有权值，这样的图称为有权
图。

一、如何做图

1.运用以下这个网站作图：

https://csacademy.com/app/graph_editor/

一开始先输入几个点的标号。他就会生成对应的点。

之后再通过“X Y Z”的输入格式，在图上绘制出：从X向Y连接，并且权重为Z的箭头。

而此处的“0-Index”和“1-Index”表示的是从0开始标号还是从1开始标号。

那么这样我们就可以做出一个非常美观的图了。保存后就可以加在我们的论文中了。

2.Matlab也可以绘制这样的图：

%% 注意：以下代码需要较新版本的matlab才能运行（最好是2016版本及以上哦）
% 如果运行出错请下载新版的matlab代码再运行

%% Matlab作无向图
% （1）无权重（每条边的权重默认为1）
% 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并生成一个图
% s 和 t 都必须具有相同的元素数；这些节点必须都是从1开始的正整数，或都是字符串元胞数组。
s1 = [1,2,3,4];
t1 = [2,3,1,1];
G1 = graph(s1, t1);
plot(G1)
% 注意哦，编号最好是从1开始连续编号，不要自己随便定义编号
s1 = [1,2,3,4];
t1 = [2,3,1,1];
G1 = graph(s1, t1);
plot(G1)

% 注意字符串元胞数组是用大括号包起来的哦
s2 = {'学校','电影院','网吧','酒店'};
t2 = {'电影院','酒店','酒店','KTV'};
G2 = graph(s2, t2);
plot(G2, 'linewidth', 2)  % 设置线的宽度
% 下面的命令是在画图后不显示坐标
set( gca, 'XTick', [], 'YTick', [] );  

% （2）有权重
% 函数graph(s,t,w)：可在 s 和 t 中的对应节点之间以w的权重创建边，并生成一个图
% 并且graph函数默认的是连续编号，不要跳跃着编号，不然会出现孤立点。并且Matlab这个函数也只能从0开始编号。
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = graph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) 
set( gca, 'XTick', [], 'YTick', [] );  

%% Matlab作有向图
% 无权图 digraph(s,t)
s = [1,2,3,4,1];
t = [2,3,1,1,4];
G = digraph(s, t);
plot(G)
set( gca, 'XTick', [], 'YTick', [] );  

% 有权图 digraph(s,t,w)
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = digraph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) 
set( gca, 'XTick', [], 'YTick', [] );  

G1绘制如下：

Matlab做出来的图不是很漂亮，要是节点比较少，还是推荐大家使用在线作图。

二、权重邻接矩阵

1.无向图的权重邻接矩阵

带权重的四个节点的无向图

无向图对应的权重邻接矩阵

结论：

1. 无向图对应的权重邻接矩阵D是一个对 称矩阵；
2. 其主对角线上元素为0.
3. 𝐷ij表示第i个节点到第j个节点的权重

2.有向图的权重邻接矩阵

带权重的四个节点的有向图

有向图对应的权重邻接矩阵

结论：

1. 有向图对应的权重邻接矩阵D是一般不 再是对称矩阵；
2. 其主对角线上元素为0.
3. 𝐷ij表示第i个节点到第j个节点的权重。

三、迪杰斯特拉算法

步骤演示：
以下是一个无向有权图


我们一共要先设置两个集合：
一个集合是我们已经访问的点，一个是我们还没有访问的点。
已经访问的点集：一开始是空集
没有访问的点集：一开始是全集

当我们开始访问节点0的时候，节点0到1和7的距离分别变成了4和8。根据最短距离优先，我们当然是要先访问1这个节点。

此时我们更新两个点集：
已经访问的点集：{0，1}
没有访问的点集：{2，3，4，5，6，7，8}
并且0和1两个节点的根节点都是0节点。

当我们的点集中有两个点的时候我们可以比较这两个点距离外部点集各自的距离，谁是最短的，那就往哪里走。
0距离7的距离是8或者4+3=7，0距离2的距离是4+8=12。所以此时我们考虑把7这个节点纳入进来。并且7的根节点是1。


此时我们更新两个点集：
已经访问的点集：{0，1，7}
没有访问的点集：{2，3，4，5，6，8}

此时我们再次更新到每个点的距离：
到2的最短距离仍然是12，而到6的距离变味了4+3+6=13，到8的距离变成了4+3+1=8。所以此时我们再次挑选距离最短的点“8”，并且节点8的根节点是7：


此时我们更新两个点集：
已经访问的点集：{0，1，7，8}
没有访问的点集：{2，3，4，5，6}

再次更新到每个点的距离：
到2的最短距离是8+2=10，到6的最短距离仍是13。所以这次选择将2纳入考虑范围，并且节点2的根节点是8：


此时我们更新两个点集：
已经访问的点集：{0，1，7，8，2}
没有访问的点集：{3，4，5，6}

再次更新到每个点的距离：
到6的最短距离仍为13，到5的距离是14，到3的距离是17。
所以纳入“6”这个节点，并且节点6的根节点是7。

此时我们更新两个点集：
已经访问的点集：{0，1，7，8，2，6}
没有访问的点集：{3，4，5}

再次更新到每个点的距离：
到5最短距离是14，到3对短距离是17.所以访问节点5，并且节点5的根节点是2。

此时我们更新两个点集：
已经访问的点集：{0，1，7，8，2，6，5}
没有访问的点集：{3，4}

再次更新到每个点的距离：
到3的距离是17，到4的距离是24.所以我们访问节点3，并且节点3的根节点是2。


此时我们更新两个点集：
已经访问的点集：{0，1，7，8，2，6，5，3}
没有访问的点集：{4}

然后最后访问节点4即可，并且节点4的根节点是5。


此时我们更新两个点集：
已经访问的点集：{0，1，7，8，2，6，5，3，4}
没有访问的点集：{ }

则此时已全部完成。
然后就可以根据我们列表的第三行存入的信息来寻找最短路径了。
从0到4的最短路径是什么呢？
倒着看：4的根节点是5，5的根节点是2，2的根节点是8，8的根节点是7，7的根节点是1，1的根节点是0。






所以最后的路径就是：

迪杰斯特拉算法的一个缺点：
可以用于有向图，但不能处理负权重。
【例】用迪杰斯特拉算法来处理下面这个带有负权重的图我们看看会发生什么？

对于这个图来说，如果起点是1，终点是2的话，根据迪杰斯特拉算法，一定是从1直接走到2，因为从1看出去，到2的距离是2，到3的距离是3，一定是直接去2比较方便。
但是我们可以得知，由于3到2的权重是负的，所以从1到3到2这条路径所需的权重其实只有1，是小于之前的距离的。这就是迪杰斯特拉算法的问题所在。

那么如何改进呢？

四、Bellman‐Ford（贝尔曼‐福特）算法

1是起点；2是终点
刚刚改变访问状态的节点为0号节点（A）
我们要更新与0号节点相邻的节点信息（B），注意，这里的B节点是未访问的哦
更新的规则如下：
如果（A与B的距离+ A列表中的距离）小于（B列表中的距离），那么我们就将B列表中的距离更新为较小的距离，并将B的父亲节点更新为A
事实上，贝尔曼‐福特算法不再将节点区分为是否已访问的状态，因为贝尔曼‐福特模型是利用循环来进行更新权重的，且每循环一次，贝尔曼福特算法都会更新所有的节点的信息。（简单来说，就是迪杰斯特拉算法是基于贪婪原则的，只顾眼前的利益，只看离自己最近的一步，但是贝尔曼‐福特算法每更新一次会把所有的点的距离重新算一遍，而不是只看眼前这一步）
注：贝尔曼‐福特算法不支持含有负权回路的图（其实大多数算法都不可以）
有兴趣的同学可以参考下面两份资料弄懂其实现原理：
https://blog.csdn.net/a8082649/article/details/81812000
https://www.bilibili.com/video/av43217121

那么什么是负权回路呢：（稍微了解即可，一般不会涉及）
在一个图里每条边都有一个权值（有正有负)
如果存在一个环（从某个点出发又回到自己的路径），而且这个环上所有权值之和是负数，那这就是一个负权环，也叫负权回路。
存在负权回路的图是不能求两点间最短路的，因为只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。
含有负权重的无向图都是负权回路。
例如下图，可以在2‐3之间无限循环。

注意：
贝尔曼‐福特算法实际上处理的是具有负权重的有向图。
（且该有向图也不能含有负权回路）
庆幸的是，含有负权重的图特别少见，且一旦出现负权重，也往往是在有向图中。
因此大家不用担心算法求解不出来的问题。

五、MATLAB实践

Matlab计算最短路径

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

功能：返回图G中start节点到end节点的最短路径 输入参数：
（1）G ‐ 输入图（graph 对象 | digraph 对象）
（2）start 起始的节点
（3）end 目标的节点
（4）[,‘Method’,algorithm]是可选的参数，表示计算最短路径的算法。一般我 们不用手动设置，默认使用的是“auto”,
输出参数：
（1）P – 最短路径经过的节点
（2）d – 最短距离

可选的算法：

1. ‘auto’（默认值）：
   ‘auto’ 选项会自动选择算法： •‘unweighted’ 用于没有边权重的 graph 和digraph 输入。 •‘positive’ 用于具有边权重的所有 graph 输入，并要求权重为非负数。此选项还用于具有非负边权重的digraph 输入。 •‘mixed’ 用于其边权重包含某些负值digraph 输入。图不能包含负循环。
2. ‘unweighted’ ：
   广度优先计算，将所有边权重都视为 1。
3. ‘positive’ ：
   Dijkstra 算法，要求所有边权重均为非负数。
4. ‘mixed’（仅适用于 digraph） ：
   适用于有向图的 Bellman‐Ford 算法，要求图没有负循环。 尽管对于相同的问题，‘mixed’ 的速度慢于 ‘positive’，但 ‘mixed’ 更为通用，因为它允许某些边权重为负数。

返回任意两点的距离矩阵

d = distances(G [,'Method',algorithm])

找给定范围内所有的点

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

返回图形 G 中与节点 s 的距离在 d 之内的所有节点。
nodeIDs是符合条件的节点
Dist是这些节点与s的距离

下面是全部代码：

%% 注意：以下代码需要较新版本的matlab才能运行（最好是2016版本及以上哦）
% 如果运行出错请下载新版的matlab代码再运行

% 注意哦，Matlab中的图节点要从1开始编号，所以这里把0全部改为了9
% 编号最好是从1开始连续编号，不要自己随便定义编号
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)  %注意：该函数matlab2015b之后才有哦

% 在图中高亮我们的最短路径
myplot = plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2);  %首先将图赋给一个变量
highlight(myplot, P, 'EdgeColor', 'r')   %对这个变量即我们刚刚绘制的图形进行高亮处理（给边加上r红色）

% 求出任意两点的最短路径矩阵
D = distances(G)   %注意：该函数matlab2015b之后才有哦
D(1,2)  % 1 -> 2的最短路径
D(9,4)  % 9 -> 4的最短路径

% 找出给定范围内的所有点  nearest(G,s,d)
% 返回图形 G 中与节点 s 的距离在 d 之内的所有节点
[nodeIDs,dist] = nearest(G, 2, 10)   %注意：该函数matlab2016a之后才有哦


% % 注意：代码文件仅供参考，一定不要直接用于自己的数模论文中
% % 国赛对于论文的查重要求非常严格，代码雷同也算作抄袭