查找图中的最短路径¶
在这个示例中，我们将使用Graphs.jl 库的函数创建一个图形，并找出图形上两点之间的最短路径。
使用图形¶
在物流、运输、信息或社交网络以及其他相关系统中，图形经常被用作模型的元素。它们是由顶点（vertex，顶点）和边（edges）组成的抽象数学对象。通常，每个顶点都有一个唯一的编号，而边则用两个数字表示--即它们所连接的顶点的编号。
Pkg.add(["GraphRecipes", "Graphs"])
# Если библиотека у вас установлена, закомментируйте следующую строчку:
import Pkg; Pkg.add( ["Graphs", "GraphRecipes"] )
using Graphs, GraphRecipes
软件包 GraphsRecipes.jl 负责绘制图形。
让我们创建一个有三个节点和几条边的简单有向图。
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 的节点编号（顶点数，即顶点数）。
创建地图，在地图上搜索路径¶
作为寻找最短路径的领域，我们将采用一个随机矩阵，并设定沿着主对角线穿越矩阵的目标。当然，除了选择 "正确 "的伪随机数发生器起始值Random.seed!() 之外，我们无法确保这张 "地图 "的连通性以及从 A 点到达 B 点的可能性。
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 )
我们的图将是不定向的，也就是说，沿着每条边，既可以到达那里，也可以返回那里。
g = Graph();
индексы_доступных_точек = LinearIndices( карта )[ карта .== 1 ]
println( "Количество площадок, куда можно наступать: ", count(индексы_доступных_точек .> 0 ))
辅助对象（坐标转换）¶
让我们保存一个矩阵，其中将存储所有地图点的二维坐标。
координаты_всех_точек = CartesianIndices( size(карта) );
创建一个图形，将图形顶点编号转换为坐标：
координаты_точек_графа = Dict(zip( 1:length(индексы_доступных_точек), координаты_всех_точек[индексы_доступных_точек] ))
first( sort(collect(координаты_точек_графа)), 5 )
现在--反转这个字典，就能将坐标转换为图形中的点号。
индексы_точек_по_координатам = Dict(value => key for (key, value) in координаты_точек_графа)
first( sort(collect(индексы_точек_по_координатам)), 5 )
让我们将点坐标添加到数组xx 和yy - 我们将把它们传递给图形绘制过程。
xy = Tuple.(first.(sort(collect(индексы_точек_по_координатам))));
xx = first.(xy);
yy = last.(xy);
填充图形¶
由于我们将使用一个标准函数来查找最短路径，而不是自己从头开始创建，因此我们需要创建一个图来进行查找。
g = Graph()
add_vertices!( g, length(координаты_всех_точек[ индексы_доступных_точек ][:]) )
让我们遍历所有点，如果它们之间有通道，就将它们连接到相邻点。
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
看看我们的图中是否添加了边以及添加了多少条边：
g
从输出结果来看，在 634 个点上添加了 840 条边。让我们显示图形：
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) )
我们无需 "展开 "图形，因为我们已经知道了每个节点的坐标。其他绘制参数可在 此处学习。
寻找最短路径¶
我们使用 A-star 算法，它利用启发式方法搜索最短路径。输出结果是一组边。
# Нахождение кратчайшего пути
path = a_star( g, индексы_точек_по_координатам[точка_А], индексы_точек_по_координатам[точка_Б] );
first( path, 5 )
让我们制作一个从 A 点到 B 点所需访问的图点数组。
points = Tuple.( vcat([точка_А], [ координаты_точек_графа[dst(v)] for v in path ]) );
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 )
结论¶
图形是非常强大的数学对象，可以让您在不同的数据中找到结构 - 循环、树、最短或最长路径以及连接区域。在动态系统建模环境中使用图形为工程师提供了非常有趣的可能性。