数模打怪（八）之图论模型
一、作图
图的数学语言描述：
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)