数模打怪（八）之图论模型

一、作图

图的数学语言描述：

G( V(G), E(G) )，G（graph）：图，V（vertex）：顶点集，E（edge）：边集

1、在线作图

https://csacademy.com/app/graph_editor

2、matlab作图

%1、无权重
%graph(s,t): 可在s和t的对应节点之间生成边，从而连成一个图
%s和t必须有相同的元素个数，这些元素的值是1,2,3...（连续正整数），或者是字符串元胞数组
 
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)
%'EdgeLabel' 是一个参数，用于指定边的标签
%G.Edges.Weight 获取图 G 中每条边的权重，并将这些权重作为边的标签进行显示
plot(G,'EdgeLabel',G.Edges.Weight,'LineWidth',2)
set(gca,'XTick',[],'YTick',[])
 
%有向图，把graph换成digraph即可
s1=[1,2,3,4,1,2]
t1=[2,3,1,1,4,2]
G1=digraph(s1,t1)
plot(G1)

二、Dijkstra算法计算最短路径

1、计算方法（流程图）

 关键点：

• 贪心策略：每次选择当前距离起点最近的点，这个选择是最优的，逐步扩展最短路径集合。
• 优先队列：通常使用一个优先队列（如最小堆）来高效地找到当前距离最近的点。

2、该算法的缺点

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

不能处理负权重（虽然可以用于有向图） 

3、matlab代码

（1）计算最短路径

 （2）计算距离矩阵 

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

 

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)
myplot=plot(G,'EdgeLabel',G.Edges.Weight,'LineWidth',2) %将图赋给一个变量
highlight(myplot,P,'EdgeColor','red') %在图中高亮出最短路径
set(gca,'XTick',[],'YTick',[])
[P,d]=shortestpath(G,9,4)
 
%求出任意两点的最短路径矩阵
D=distances(G)
D(1,2) %1->2的最短路径
D(9,4) %9->4的最短路径
 
%找出给定范围内的所有点 nearest(G,s,d)
%返回图G中与节点s的距离在d之内的所有节点
[nodelDs,dist]=nearest(G,2,10)