数学建模学习笔记（8）：图论最短路径问题

三种常用的最短路径算法

最短路径问题是图论中的一个重要课题。常用的三种最短路径求解算法分别是：迪杰斯特拉算法、贝尔曼福特算法和弗洛伊德算法。

迪杰斯特拉算法步骤

迪杰斯特拉算法是一种标号法，其步骤为：

1. 将图终所有顶点分为已确定和未确定两部分，起初已确定部分的结点为空，所有的顶点都属于未确定的顶点。
2. 选定一个结点作为出发点。
3. 每次寻找与上一步选择结点相邻的那些结点并记录局部最短路径距离，从中寻找最小值作为下一步的出发点。
4. 重复上述过程，直到所有顶点都已经确定。

迪杰斯特拉算法的评价

迪杰斯特拉算法可以处理无向图也可以处理有向图，但是迪杰斯特拉算法的缺点之一是一般不能用于处理带有负权边的图。

贝尔曼福特算法

贝尔曼福特算法可以处理带有负权边的图。相比于迪杰斯特拉算法的贪婪策略，贝尔曼福特算法利用循环来更新权重，并且每循环一次都会更新所有结点的信息，因此效率上会低于迪杰斯特拉算法。贝尔曼福特算法的缺点是不支持含有负权回路的图。负权回路是指权值之和是负数的回路。

最短路径算法的实现

可以使用Matlab处理图的最短路径问题，并可以自由选择选择使用迪杰斯特拉算法或贝尔曼福特算法。Matlab还可以直接返回图中任意两点之间最短距离的矩阵，以及判断最短距离在一定距离内的所有结点编号。

弗洛伊德算法

弗洛伊德算法可以通过一次运行求解出任意两点之间的最短路径，但是该算法的时间复杂度也高于其他的两种算法，其核心是三层循环。

图论中的作图问题

关于图论问题的作图，可以使用课程推荐的在线作图网站，也可以使用Matlab进行完成。

相关Matlab代码介绍

一些常用的相关Matlab函数介绍：

%% 第六节课：图论中的最短路径问题

% 1.Matlab无向图图函数graph()与有向图图函数digraph()：
% ①当参数个数为两个时，语法为：graph/digraph（s,t）
%   其中s和t分别为两个点集，其中的元素个数要求相同，可以是从1开始的一系列整数，也可以是用大括号封闭的一个元胞数组（其中元素为字符串）
  s=[1,2,3,4];t=[4,3,2,1];
  G1=graph(s,t);figure(1);plot(G1)
  G2=digraph(s,t);figure(2);plot(G2)
% ②第三个参数为边的权重（默认每条边的权重为1），是一个与点集元素个数相同的数组，画图时标出权重的方式：plot(图名，'Edgelabel',图名.Edges.Weight)
   s=[1,2,3,4];t=[4,3,2,1];w=[1,2,3,4];
   G=graph(s,t,w);plot(G,'Edgelabel',G.Edges.Weight)

% 2.隐藏坐标轴名称的方法（与plot函数搭配使用）：set（gca，'XTick',[],'YTick',[])
  s=[1,2,3,4];t=[2,3,4,1];w=[1,2,3,4];
  G=graph(s,t,w);plot(G,'Edgelabel',G.Edges.Weight)
  set(gca,'XTick',[],'YTick',[]);
  
% 3.求最短路径的函数shortestpath（）：语法：shortestpath(图变量名，起点，终点,['Method',算法])
% 其中的图可以是无向图或者有向图，最后的算法是可选参数，默认采用自动选择的方式，输出两个参数，分别表示最短路径经过的结点和最短路径长度
% 可选的算法有：unweighted：广度优先计算（将所有边的权重均视为1） positive：迪杰斯特拉算法，要求边的权重均为非负数
%               mixed：贝尔曼-福特算法，效率比迪杰斯特拉算法低，但是适用范围更广。
  s=[1,2,3,4];t=[2,3,4,1];w=[1,2,3,4];G=graph(s,t,w);
  [path,length]=shortestpath(G,1,3)

% 4.高亮标出最短路径的方式：使用函数highlight()：语法：highlight（图像名，最长路径名，’EdgeColor',颜色）
  s=[1,2,3,4];t=[2,3,4,1];w=[1,2,3,4];G=graph(s,t,w);
  [path,length]=shortestpath(G,1,3);
  Plot=plot(G,'linewidth',3);highlight(Plot,path,'EdgeColor','r')
  
% 5.求任意两点之间的最短距离的矩阵的函数distances()：语法：distances（图名，['Method',算法]）
  s=[1,2,3,4];t=[2,3,4,1];w=[1,2,3,4];G=graph(s,t,w);
  distances(G)
  
% 6.找出给定距离范围内的所有节点的函数nearest()：语法：nearest（图名，结点，距离，['Method',算法]）
%   返回两个列向量[Nodes,Dists]，分别表示满足条件的结点以及它们所对应的最短距离
   s=[1,2,3,4];t=[2,3,4,1];w=[1,2,3,4];G=graph(s,t,w);
   [Nodes,Dists]=nearest(G,1,5)

% 7.输出警告信息的函数warning():语法：warning（警告提示字符串）
  warning("输入错误，请重新输入！")

% 8.用于退出函数的return语句：在自定义函数的定义体中使用，可以直接退出当前函数
  return

% 9.记录程序运行时间的方法
  tic;  %开始计时
  toc;  %停止计时
  
% 10.修改Matlab数字计算结果的格式为长数字形式（不使用则采用默认的四位小数或科学计数法形式）
  format long g
  
% 11.无穷大数字的表示方法
  inf
  
% 12.求两个整数相除的余数
% mod(被除数,除数)
mod(100,14)

% 13.设置绘图中横轴和纵轴的范围
% axis([x1 x2 y1 y2])：其中x1表示x的下限，x2表示x的上限；y1表示y的下限，y2表示y的上限
x=1:0.01:3;
y=2*x;
plot(x,y)
axis([1 4 2 8]);

% 14.设置程序暂停
% pause(暂停时间)：暂停时间用秒计算
pause(3)

% 15.在图中指定坐标处标注文本
% text(横坐标,纵坐标,文本内容)
text(2,4,"示例");
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72