Engee 文档
Notebook

在图上查找最短路径

在这个例子中，我们将使用库函数。 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 ))。

In [ ]: 
Pkg.add(["GraphRecipes", "Graphs"])
In [ ]: 
# Если библиотека у вас установлена, закомментируйте следующую строчку:
import Pkg; Pkg.add( ["Graphs", "GraphRecipes"] )
In [ ]: 
using Graphs, GraphRecipes

让我们创建一个包含三个节点和几个边的简单有向图。

In [ ]: 
g = DiGraph()
add_vertices!( g, 3 );

现在我们的图中有三个顶点，用边连接它们。

In [ ]: 
add_edge!( g, 1, 2 );
add_edge!( g, 1, 3 );
add_edge!( g, 2, 3 );

我们将输出这张图:

In [ ]: 
gr() # Упрощенная отрисовка
graphplot( g, names=1:nv(g) )
Out[0]:

请注意，节点名称为 names 取自"外部"数组 1:nv(g)，从哪里存储的节点号 1 以前 nv （顶点数，顶点数）。

##让我们创建一个地图，我们将寻找一条路

作为寻找最短路径的领域，我们将采取一个随机矩阵，并设定一个目标，沿着它沿着主对角线行走。 这个"地图"的连通性和从a点到达B点的能力，唉，除了选择伪随机数生成器的"正确"起始值之外，其他任何东西都没有提供。 Random.seed!().

In [ ]: 
using Random;
Random.seed!( 4 )

карта = rand( 30, 30 ) .> 0.3;
heatmap( карта )

# Точка старта и финиша
точка_А = CartesianIndex(1,1)
точка_Б = CartesianIndex(30,30)

# Добавим на график токи старта и финиша
scatter!( [точка_А[1]], [точка_А[2]], c=:red )
scatter!( [точка_Б[1]], [точка_Б[2]], c=:green, leg=false )
Out[0]:

我们的图将是无向的，也就是说，沿着每个边缘，可以同时去那里和回来。

In [ ]: 
g = Graph();
индексы_доступных_точек = LinearIndices( карта )[ карта .== 1 ]
println( "Количество площадок, куда можно наступать: ", count(индексы_доступных_точек .> 0 ))

Количество площадок, куда можно наступать: 634

辅助对象（坐标平移）

让我们保存将存储地图上所有点的2D坐标的矩阵。

In [ ]: 
координаты_всех_точек = CartesianIndices( size(карта) );

让我们创建一个图形，将图形的顶点编号转换为坐标:

In [ ]: 
координаты_точек_графа = Dict(zip( 1:length(индексы_доступных_точек), координаты_всех_точек[индексы_доступных_точек] ))
first( sort(collect(координаты_точек_графа)), 5 )
Out[0]:
5-element Vector{Pair{Int64, CartesianIndex{2}}}:
 1 => CartesianIndex(1, 1)
 2 => CartesianIndex(2, 1)
 3 => CartesianIndex(3, 1)
 4 => CartesianIndex(4, 1)
 5 => CartesianIndex(5, 1)

现在我们反转这个字典，并有机会将坐标转换为图形上的点数。

In [ ]: 
индексы_точек_по_координатам = Dict(value => key for (key, value) in координаты_точек_графа)
first( sort(collect(индексы_точек_по_координатам)), 5 )
Out[0]:
5-element Vector{Pair{CartesianIndex{2}, Int64}}:
 CartesianIndex(1, 1) => 1
 CartesianIndex(2, 1) => 2
 CartesianIndex(3, 1) => 3
 CartesianIndex(4, 1) => 4
 CartesianIndex(5, 1) => 5

将点的坐标添加到数组中 xx 和 yy –我们会将它们转移到图形渲染程序。

In [ ]: 
xy = Tuple.(first.(sort(collect(индексы_точек_по_координатам))));
xx = first.(xy);
yy = last.(xy);

填写图表

由于我们将使用标准函数来查找最短路径，而不是自己从头开始创建它，因此我们需要创建一个将进行此搜索的图形。

In [ ]: 
g = Graph()
add_vertices!( g, length(координаты_всех_точек[ индексы_доступных_точек ][:]) )
Out[0]:
634

让我们通过所有的点，并将它们与相邻的点连接起来，如果它们之间有一个通道。

In [ ]: 
MAX_X,MAX_Y = size( карта )

for вершина in 1:nv(g)
    x,y = Tuple(координаты_точек_графа[вершина])
    точка_справа = CartesianIndex( x + 1, y )
    точка_снизу = CartesianIndex( x, y + 1 )
    
    # Соединим текущую точку с точкой справа, если есть связанность согласно карте пройденных точек 
    if x < MAX_X && карта[точка_справа] == 1 add_edge!(g, вершина, индексы_точек_по_координатам[точка_справа]); end;
    # То же самое для точки снизу
    if y < MAX_Y && карта[точка_снизу] == 1 add_edge!(g, вершина, индексы_точек_по_координатам[точка_снизу]); end;
end

让我们看看是否有任何边被添加到我们的图表中，以及有多少边被添加到我们的图表中:

In [ ]: 
g
Out[0]:
{634, 871} undirected simple Int64 graph

从输出来看，840个边缘被添加到634个点。 让我们输出一个图表:

In [ ]: 
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) )
Out[0]:

我们不必"布局"图形，因为我们已经知道每个节点的坐标。 其余的渲染参数可以研究[这里]（https://juliagraphs.org/GraphPlot.jl /)。

寻找最短路径

我们使用[a-star算法]（https://juliagraphs.org/Graphs.jl/dev/algorithms/shortestpaths /），其中使用启发式搜索最短路径。 在输出端，我们得到一组边缘。

In [ ]: 
# Нахождение кратчайшего пути
path = a_star( g, индексы_точек_по_координатам[точка_А], индексы_точек_по_координатам[точка_Б] );
first( path, 5 )
Out[0]:
5-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 2 => 27
 Edge 27 => 51
 Edge 51 => 52
 Edge 52 => 79

让我们制作一个从a点到B点需要访问的图形点数组。

In [ ]: 
points = Tuple.( vcat([точка_А], [ координаты_точек_графа[dst(v)] for v in path ]) );
first( points, 5 )
Out[0]:
5-element Vector{Tuple{Int64, Int64}}:
 (1, 1)
 (2, 1)
 (2, 2)
 (2, 3)
 (3, 3)
In [ ]: 
# Вывод карты (со смещенными значениями для нужной яркости графика)
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 )
Out[0]:

结论

图形是非常强大的数学对象，允许您在不同的数据周期，树，最短或最长路径以及连接区域中查找结构。 在动态系统建模环境中与他们合作的机会为工程师提供了非常有趣的机会。