数学建模 图论最短路径问题
程序员文章站
2023-12-27 14:04:33
...
1、图的基本概念
图论中的图(Graph)是由若干给定的点及连接两点的线 所构成的图形,这种图形通常用来描述某些事物之间的某种 特定关系,用点代表事物,用连接两点的线表示相应两个事 物间具有这种关系。
一个图可以用数学语言描述为G(V(G),E(G))。V(vertex)指 的是图的顶点集,E(edge)指的是图的边集。根据边是否有方向,可将图分为有向图(图一)和无向图(图二)。另外,有些图的边上还可能有权值,这样的图称为有权图(图三)。
2、作图
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', [] );
3、无向图的权重邻接矩阵
4、迪杰斯特拉算法
在线观看算法
缺点:不能计算带有负权重的图
5、Bellman‐Ford(贝尔曼‐福特)算法
刚刚改变访问状态的节点为0号节点(A) 我们要更新与0号节点相邻的节点信息(B),注意, 这里的B节点是未访问的哦 更新的规则如下: 如果(A与B的距离+ A列表中的距离)小于(B列表中 的距离),那么我们就将B列表中的距离更新为较小的 距离,并将B的父亲节点更新为A
事实上,贝尔曼‐福特算法不再将节点区分为是否已 访问的状态,因为贝尔曼‐福特模型是利用循环来进 行更新权重的,且每循环一次,贝尔曼福特算法都会 更新所有的节点的信息。
贝尔曼‐福特算法不支持含有负权回路的图。 (Floyd(弗洛伊德)算法也不可以)
负权回路:在一个图里每条边都有一个权值(有正有负) 如果存在一个环(从某个点出发又回到自己的路径),而且 这个环上所有权值之和是负数,那这就是一个负权环,也叫负权 回路。存在负权回路的图是不能求两点间最短路的,因为只要在负 权回路上不断兜圈子,所得的最短路长度可以任意小。
6、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之后才有哦