数学建模（NO.13图论最短路径问题）_最短路径数学建模案例

一.图的基本概念

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

二.绘图方法

1.绘图网站

绘图

2. 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的权重创建边，并生成一个图
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', [] );  
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

三.权重邻接矩阵

1.无向图

2.有向图

四.迪杰斯特拉算法

图中有0‐8共九个地点，地点之间若用直线连接则表明两地可直接到达，直线旁的数值表示两地的距离。
问题: 起点为0，终点为4，怎么走路程最短

4  5  2  8  7  1  0

五.迪杰斯特拉算法的一个缺点

可以用于有向图，但不能处理负权重

六.Bellman‐Ford（贝尔曼‐福特）算法

刚刚改变访问状态的节点为0号节点（A）
我们要更新与0号节点相邻的节点信息（B），注意，这里的B节点是未访问的哦
=更新的规则如下：
如果（A与B的距离+ A列表中的距离）小于（B列表中的距离），那么我们就将B列表中的距离更新为较小的距离，并将B的父亲节点更新为A
事实上，贝尔曼‐福特算法不再将节点区分为是否已访问的状态，因为贝尔曼‐福特模型是利用循环来进行更新权重的，且每循环一次，贝尔曼福特算法都会更新所有的节点的信息。

贝尔曼‐福特算法不支持含有负权回路的图。 （视频中提到的Floyd(弗洛伊德)算法也不可以）

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

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

七.Matlab计算最短路径

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

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

八.可选的算法

九.实例

1. 返回任意两点的距离矩阵

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

2.找给定范围内所有的点

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

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