在图上查找最短路径
在这个例子中，我们将使用库函数。 Graphs.jl 要创建一个图形，并找到它的两个点之间的最短路线。
使用图表
图形通常用作物流，运输，信息或社交媒体任务以及其他相关系统中的模型元素。 它们是由顶点（顶点，顶点）和边（边）组成的抽象数学对象。 通常，每个顶点都有自己的唯一编号，边由两个数字表示–它们连接的顶点的数字。
一些信息可以与节点和边（例如，坐标或带宽）相关联。 在库[Graphs.jl](https://github.com/JuliaGraphs/Graphs.jl?tab=readme-ov-file ）假设附加信息存储在外部表或字典（Dict）中。 记录可以链接到顶点（通过它们的数字）或边（通过标识边的数字元组）。 稀疏矩阵可以用来省钱（[SparseArrays.jl]（https://engee.com/helpcenter/stable/julia/stdlib/SparseArrays.html ))。
Pkg.add(["GraphRecipes", "Graphs"])
# 如果您安装了库，请在以下行中注释:
import Pkg; Pkg.add( ["Graphs", "GraphRecipes"] )
using Graphs, GraphRecipes
包[GraphsRecipes.jl](https://engee.com/helpcenter/stable/julia/juliaplots/GraphRecipes/introduction.html ）负责绘制图形。
让我们创建一个包含三个节点和几个边的简单有向图。
g = DiGraph()
add_vertices!( g, 3 );
现在我们的图中有三个顶点，用边连接它们。
add_edge!( g, 1, 2 );
add_edge!( g, 1, 3 );
add_edge!( g, 2, 3 );
我们将输出这张图:
gr() # 简化渲染
graphplot( g, names=1:nv(g) )
请注意，节点的名称为 names 取自"外部"数组 1:nv(g)，从哪里存储的节点号 1 以前 nv （顶点数，顶点数）。
##让我们创建一个地图，我们将寻找一条路
作为寻找最短路径的领域，我们将采取一个随机矩阵，并设定一个目标，沿着它沿着主对角线行走。 这个"地图"的连通性和从a点到达B点的能力，唉，除了选择伪随机数生成器的"正确"起始值之外，其他任何东西都没有提供。 Random.seed!().
using Random;
Random.seed!( 4 )
地图=兰德（30，30）。> 0.3;
热图(地图)
# 起点和终点
DOT_A=CartesianIndex（1,1）
DOT_B=CartesianIndex（30,30）
# 让我们将开始和结束电流添加到图表中。
散开！([DOT_A[1]],[dot_a[2]],c=:红色)
散开！([DOT_B[1]],[dot_b[2]],c=:green,leg=false)
我们的图将是无向的，也就是说，沿着每个边缘，可以同时去那里和回来。
g = Graph();
可用点的索引=LinearIndices(map)[地图。== 1 ]
println( "您可以踩到的平台数量: ", count(индексы_доступных_точек .> 0 ))
辅助对象（坐标平移）
让我们保存将存储地图上所有点的2D坐标的矩阵。
所有点的坐标=CartesianIndices（大小（地图））;
让我们创建一个图形，将图形的顶点编号转换为坐标:
图的点坐标=Dict(zip(1:length(indexes of available points),coordinates of all points[indexes of available points]))
首先（排序（收集（point_graph坐标）），5）
现在我们反转这个字典，并有机会将坐标转换为图形上的点数。
point_points by coordinates=Dict(value=>key for(key,value)in point_graph坐标)
首先（sort（collect（point_indexes by coordinates）），5）
将点的坐标添加到数组中 xx 和 yy –我们会将它们转移到图形渲染程序。
xy=元组。（第一。（sort（collect（point_indexes by coordinates））））;
xx = first.(xy);
yy = last.(xy);
填充图形
由于我们将使用标准函数来查找最短路径，而不是自己从头开始创建它，因此我们需要创建一个将进行此搜索的图形。
g = Graph()
add_vertices！（g，长度（所有点的坐标[可用点的索引][：]））
让我们通过所有的点，并将它们与相邻的点连接起来，如果它们之间有一个通道。
MAX_X,MAX_Y=大小(地图)
对于顶点在1：nv（g）
x,y=元组（图[顶点]的点坐标）
right_point=CartesianIndex（x+1，y）
point_side=CartesianIndex（x，y+1）
# 将当前点连接到右侧的点，如果根据通过的点的地图有连接。
如果x<MAX_X&&map[access point]==1add_edge！(g,vertex,point_indication_coordinates[right_point]);end;
# 对于来自下面的点也是如此
如果y<MAX_Y&&map[指向下]==1add_edge！(g,vertex,point_indexs_coordinates[point_side]);end;
end
让我们看看边缘是否已添加到我们的图中，以及有多少边:
g
从输出来看，840个边缘被添加到634个点。 让我们输出一个图表:
heatmap( карта', title="地图", titlefont=font(9), leg=:false )
graphplot!( g, x = xx, y = yy, nodeshape=:circle, nodecolor=:red, nodestrokecolor=:red, nodesize=1.5, edgecolor=:red, curves=true, size=(500,500) )
我们不必"布局"图形，因为我们已经知道每个节点的坐标。 其余的渲染参数可以研究[这里]（https://juliagraphs.org/GraphPlot.jl /)。
寻找最短路径
我们使用[a-star算法]（https://juliagraphs.org/Graphs.jl/dev/algorithms/shortestpaths /），其中使用启发式搜索最短路径。 在输出端，我们得到一组边缘。
# 寻找最短路径
path=a_star(g,索引指向坐标[点A],索引指向坐标[点B]);
first( path, 5 )
让我们制作一个从a点到B点需要访问的图形点数组。
点=元组。(vcat([点A],[点坐标[dst(v)]为v在路径]));
first( points, 5 )
# 地图输出（具有所需图形亮度的偏移值）
heatmap( карта' .* 0.3 .+ 0.7, title="最短路径", leg=false, c=:grays, aspect_ratio=:equal )
# 在地图上可接受运动的图形的输出
# graphplot!( g, x = xx, y = yy, curves=true, nodeshape=:circle, size=(400,400) )
# 推导最短路径
plot!( first.(points), last.(points), lw=3, linez=range(0,1,length(points)), c=:viridis, yflip=true )
结论
图形是非常强大的数学对象，允许您在不同的数据周期，树，最短或最长路径以及连接区域中查找结构。 在动态系统建模环境中与他们合作的机会为工程师提供了非常有趣的机会。