Сообщество Engee
Engee Community
/
Примеры и проекты
/
Нахождение кратчайших путей в графе по алгоритму Дийкстры

Нахождение кратчайших путей в графе по алгоритму Дийкстры

Автор
avatar-nadezhdatarnadezhdatar
Notebook

Нахождение кратчайших путей в графе, используя алгоритм Дийкстры

Создание графа на примере транспортной сети из матрицы смежности, считанной с Excel. Нахождение кратчайших путей в "прыжках" и расстояниях с помомощью алгоритма Дийкстры. Запись результат в Excel.

Описание задачи

Имеется автомобильная транспортная сеть (см. рисунок). имеется Excel-файл, в котором занесена информация о данной транспортной сети в виде матрицы смежности и таблицы с расстояниями между узлами сети.
Транспортная сеть – ненаправленный граф, т.е. по ребру можно перемещаться в прямом и обратном напрявлениях. Помимо того что графы могут быть направленными или ненаправленными, они могут быть также взвешенными или невзвешенными. Взвешенный граф — это такой граф, у которого с каждым из ребер связано некое сопоставимое значение, обычно числовое. В потенциальной транспортной сети вес ребер – это расстояния между узлами.
Задача заключается в поиске оптимальных путей между узлами (вершинами) в «прыжках» на невзвешенном графе и в расстояниях на взвешенном графе. За чем это надо?
Если бы вид транспорта на данной транспортной сети был бы настолько быстрый по скорости, то для оптимизации времени в пути между узлами, вероятно, потребуется считать количество ребер, так как расстояние между ними имеет гораздо меньшее значение, чем то, сколько прыжков потребуется (сколько узлов придется посетить), чтобы добраться от узла до другого. Каждая станция может означать задержку, поэтому, как и при полетах на самолете, чем меньше остановок, тем лучше.

In [ ]: 
img = load( "$(@__DIR__)/pics/ОТС_без карты.jpg" )
Out[0]:
No description has been provided for this image

Алгоритм Дийкстры (англ. Dijkstra’s algorithm) —

алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

In [ ]: 
using Pkg
Pkg.add("GraphRecipes")
In [ ]: 
Pkg.add("SimpleWeightedGraphs")
In [ ]: 
Pkg.add("GraphPlot")
In [ ]: 
using Graphs, GraphRecipes, GraphPlot, SimpleWeightedGraphs
In [ ]: 
using XLSX, Plots

Поиск кратчайшего пути в "прыжках" на невзвешенном графе.

Считаем матрицу смежности с Excel, построим невзвешанный граф

In [ ]: 
room = Matrix(Int64.(XLSX.readdata("Data.xlsx", "Исходник", "D4:AD30"))) # Считывает данные с Excel-файла в матрицу {Int64},
# потому что SimpleGraph c {Any} у меня не работает.
Out[0]:
27×27 Matrix{Int64}:
 0  1  0  0  0  0  0  0  0  0  0  0  0  …  0  0  0  0  0  0  0  0  0  0  0  0
 1  0  1  1  0  0  0  0  0  0  0  0  0     0  0  0  0  0  0  0  0  0  0  0  0
 0  1  0  0  1  0  0  0  0  0  0  0  0     0  0  0  0  0  0  0  0  0  0  0  0
 0  1  0  0  0  0  1  0  0  0  0  0  0     0  0  0  0  1  0  0  0  0  0  0  0
 0  0  1  0  0  1  1  1  0  0  0  0  0     0  0  0  0  0  0  0  0  0  0  1  0
 0  0  0  0  1  0  0  0  0  0  0  0  0  …  0  0  0  0  0  0  0  0  0  1  0  0
 0  0  0  1  1  0  0  0  0  0  0  0  0     0  0  0  0  0  0  0  0  0  0  0  1
 0  0  0  0  1  0  0  0  0  0  0  0  1     0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  1  0  1  0     0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  1  0  1  0  0     0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  1  0  0  0  …  1  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  1  0  0  0  0     0  0  0  0  0  0  0  0  1  0  0  0
 0  0  0  0  0  0  0  1  0  0  0  0  0     1  0  0  0  0  0  0  0  0  1  0  0
 ⋮              ⋮              ⋮        ⋱  ⋮              ⋮              ⋮  
 0  0  0  0  0  0  0  0  0  0  1  0  1  …  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0     0  0  1  1  1  1  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0     0  1  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0     0  1  0  0  0  0  0  0  0  0  0  0
 0  0  0  1  0  0  0  0  0  0  0  0  0     0  1  0  0  0  0  0  0  0  0  0  1
 0  0  0  0  0  0  0  0  0  0  0  0  0  …  0  1  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0     0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0     0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  1  0     0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  1  0  0  0  0  0  0  1     0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  1  0  0  0  0  0  0  0  0  …  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  1  0  0  0  0  0  0     0  0  0  0  1  0  0  0  0  0  0  0
In [ ]: 
graph_room = SimpleGraph(room)  #Постройте SimpleDiGraph{T} из матрицы смежности adjm. Если adjm[i][j] != 0, то вставляется ребро (i, j). 
#adjm должна быть квадратной матрицей. Тип элемента T может быть опущен.

# SimpleGraph - не ориентированный граф, SimpleDiGraph - ориентированный граф.
Out[0]:
{27, 31} undirected simple Int64 graph
In [ ]: 
#  определяем кол-во вершин и ребер графа
vershiny = nv(graph_room) # Количество вершин 
rebra = ne(graph_room)   # Количество ребер 
println( "Количество вершин = ", vershiny)
println("Количество ребер = ", rebra )

Количество вершин = 27
Количество ребер = 31
In [ ]: 
# Отрисовка графа условно
graphplot(graph_room,
          markersize = 0.2,
          names = 1:vershiny,
          fontsize = 10,
          linecolor = :darkgrey
          )

#graphplot(graph_room, names=1:nv(graph_room))
Out[0]:

Например, найдем кратчайший путь в "прыжках" от любой вершины до другой вершины с помощью алгоритма Дийкстра. Перечислим путь.

In [ ]: 
path_1_24=enumerate_paths(dijkstra_shortest_paths(graph_room, 1), 24) # кратчайший путь от вершины 1 до вершины 24
Out[0]:
12-element Vector{Int64}:
  1
  2
  3
  5
  8
 13
 16
 11
 10
  9
 12
 24
In [ ]: 
path_27_1 = enumerate_paths(dijkstra_shortest_paths(graph_room, 27), 1)  # кратчайший путь от вершины 27 до вершины 1
Out[0]:
5-element Vector{Int64}:
 27
  7
  4
  2
  1
In [ ]: 
# Найдем за сколько "прыжков" мы доберемся от вершины 27 до вершины 1.
count_jumps_27_1 = length(path_27_1)-1 # количество "прыжков"
Out[0]:
4
In [ ]: 
# найти кратчайший путь от вершины 1 до всех вершин с помощью алгоритма Дийкстра.Перечислить пути.
path_1_all = enumerate_paths(dijkstra_shortest_paths(graph_room, 1))
Out[0]:
27-element Vector{Vector{Int64}}:
 []
 [1, 2]
 [1, 2, 3]
 [1, 2, 4]
 [1, 2, 3, 5]
 [1, 2, 3, 5, 6]
 [1, 2, 4, 7]
 [1, 2, 3, 5, 8]
 [1, 2, 3, 5, 8, 13, 16, 11, 10, 9]
 [1, 2, 3, 5, 8, 13, 16, 11, 10]
 [1, 2, 3, 5, 8, 13, 16, 11]
 [1, 2, 3, 5, 8, 13, 16, 11, 10, 9, 12]
 [1, 2, 3, 5, 8, 13]
 ⋮
 [1, 2, 3, 5, 8, 13, 16]
 [1, 2, 4, 20, 17]
 [1, 2, 4, 20, 17, 18]
 [1, 2, 4, 20, 17, 19]
 [1, 2, 4, 20]
 [1, 2, 4, 20, 17, 21]
 [1, 2, 3, 5, 6, 25, 14, 22]
 [1, 2, 3, 5, 8, 13, 16, 15, 23]
 [1, 2, 3, 5, 8, 13, 16, 11, 10, 9, 12, 24]
 [1, 2, 3, 5, 6, 25]
 [1, 2, 3, 5, 26]
 [1, 2, 4, 20, 27]

Найдем количество "прыжков" от каждой вершины ко всем вершинам по кратчайшим путям

In [ ]: 
mass = [enumerate_paths(dijkstra_shortest_paths(graph_room, x)) for x in 1:vershiny] # массив из всех перечисленных путей от каждой вершине ко всем вершинам
count_jumps = zeros(vershiny,vershiny)
for i in 1:vershiny
    for j in 1:vershiny
        count_jumps[i,j] = length(mass[i][j])
        if count_jumps[i,j] > 0
            count_jumps[i,j] -= 1
        end
    end
end
count_jumps
Out[0]:
27×27 Matrix{Float64}:
  0.0   1.0  2.0   2.0  3.0  4.0  3.0  …  7.0   8.0  11.0  5.0  4.0   4.0
  1.0   0.0  1.0   1.0  2.0  3.0  2.0     6.0   7.0  10.0  4.0  3.0   3.0
  2.0   1.0  0.0   2.0  1.0  2.0  2.0     5.0   6.0   9.0  3.0  2.0   3.0
  2.0   1.0  2.0   0.0  2.0  3.0  1.0     6.0   7.0  10.0  4.0  3.0   2.0
  3.0   2.0  1.0   2.0  0.0  1.0  1.0     4.0   5.0   8.0  2.0  1.0   2.0
  4.0   3.0  2.0   3.0  1.0  0.0  2.0  …  3.0   5.0   8.0  1.0  2.0   3.0
  3.0   2.0  2.0   1.0  1.0  2.0  0.0     5.0   6.0   9.0  3.0  2.0   1.0
  4.0   3.0  2.0   3.0  1.0  2.0  2.0     3.0   4.0   7.0  2.0  2.0   3.0
  9.0   8.0  7.0   8.0  6.0  6.0  7.0     5.0   5.0   2.0  5.0  7.0   8.0
  8.0   7.0  6.0   7.0  5.0  5.0  6.0     4.0   4.0   3.0  4.0  6.0   7.0
  7.0   6.0  5.0   6.0  4.0  4.0  5.0  …  3.0   3.0   4.0  3.0  5.0   6.0
 10.0   9.0  8.0   9.0  7.0  7.0  8.0     6.0   6.0   1.0  6.0  8.0   9.0
  5.0   4.0  3.0   4.0  2.0  2.0  3.0     2.0   3.0   6.0  1.0  3.0   4.0
  ⋮                          ⋮         ⋱                        ⋮    
  6.0   5.0  4.0   5.0  3.0  3.0  4.0  …  2.0   2.0   5.0  2.0  4.0   5.0
  4.0   3.0  4.0   2.0  4.0  5.0  3.0     8.0   9.0  12.0  6.0  5.0   2.0
  5.0   4.0  5.0   3.0  5.0  6.0  4.0     9.0  10.0  13.0  7.0  6.0   3.0
  5.0   4.0  5.0   3.0  5.0  6.0  4.0     9.0  10.0  13.0  7.0  6.0   3.0
  3.0   2.0  3.0   1.0  3.0  4.0  2.0     7.0   8.0  11.0  5.0  4.0   1.0
  5.0   4.0  5.0   3.0  5.0  6.0  4.0  …  9.0  10.0  13.0  7.0  6.0   3.0
  7.0   6.0  5.0   6.0  4.0  3.0  5.0     0.0   4.0   7.0  2.0  5.0   6.0
  8.0   7.0  6.0   7.0  5.0  5.0  6.0     4.0   0.0   7.0  4.0  6.0   7.0
 11.0  10.0  9.0  10.0  8.0  8.0  9.0     7.0   7.0   0.0  7.0  9.0  10.0
  5.0   4.0  3.0   4.0  2.0  1.0  3.0     2.0   4.0   7.0  0.0  3.0   4.0
  4.0   3.0  2.0   3.0  1.0  2.0  2.0  …  5.0   6.0   9.0  3.0  0.0   3.0
  4.0   3.0  3.0   2.0  2.0  3.0  1.0     6.0   7.0  10.0  4.0  3.0   0.0

Запишем результат в файл Excel

In [ ]: 
#= 
Записывыает только результат в имеющийся файл result.xlsx, заранее подготовленный с листом "Количество_прыжков", 
где уже внесена таблица (шапочка). Файл должен быть закрыт в это время. Данные переносяться и сохраняются.
=#

XLSX.openxlsx("result.xlsx", mode="rw") do xf   # Редактирование существующего файла: режим "rw"
    sheet = xf["Количество_прыжков"]  # Обратиться к листу "Количество_прыжков" 
    sheet["D4:AD30"] = count_jumps     # записать в ячейки D4:AD30 матрицу результатов
end;

Поиск кратчайшего пути по расстояниям на взвешенном графе.

В этом примере воспользуемся функциями библиотеки SimpleWeightedGraphs.jl чтобы создать граф и найти на нем кратчайшие маршруты от всех вершин ко всем вершинам.

Взвешенный граф - граф, в котором у каждого ребра и/или каждой вершины есть “вес” - некоторое число, которое может обозначать длину пути, его стоимость и т. п.

SimpleWeightedGraphs.jl- этот пакет определяет два новых типа графиков: SimpleWeightedGraph и SimpleWeightedDiGraph. Ознакомьтесь с руководством , чтобы узнать, что вы можете с ними сделать.

Также обратитесь к пакету Graphs.jl для получения более сложных алгоритмов.

In [ ]: 
using DataFrames
In [ ]: 
#graph_room_2 = SimpleWeightedGraph(room) # SimpleWeightedGraph(adjmx) создает граф из матрицы смежности adjm.
In [ ]: 
# Считывает данные с Excel-файла в матрицу, оборачиваем матрицу в таблицу с шапочкой для наглядности.
distance = DataFrame(XLSX.readdata("Data.xlsx", "Исходные_Авто_км", "E2:G32"), ["УзелНачала", "УзелКонец", "Расстояние"])
Out[0]:

31 rows × 3 columns

УзелНачалаУзелКонецРасстояние
AnyAnyAny
112268
223240
324333
435700
54769
6420252
756136
857446
958328
10526458
11625549
12727435
13813229
14910193
15912162
161011110
171116543
18122455
191314243
201316158
211325437
221416404
23142255
241425284
251516348
26152355
271718316
281719186
29172085
30172197
⋮⋮⋮⋮
In [ ]: 
# Число узлов
n = max(maximum(distance[:,:УзелНачала]), maximum(distance[:,:УзелКонец]))
Out[0]:
27
In [ ]: 
# Число ребер
r = nrow(distance) # Число ребер (дуг) r = количеству строк в таблице
# size(isdan,1) - размер строк, то же самое будет: nrow(isdan)
Out[0]:
31

Строим взвешанный неориентированный граф

In [ ]: 
# Строим граф

#= SimpleWeightedGraphs.jl предоставляет структуру для (не) ориентированных графов 
с возможностью задания весов на ребрах. Если вам нужны веса ребер и не требуется большого количества модификаций графика,
используйте SimpleWeightedGraphs.jl  =#

graph_distance=SimpleWeightedGraph(n)    # используйте "Простой взвешенный Орграф" для неориентированных графов.
 #добавляем ребра с их расстояниями (весами)
for i=1:r
    add_edge!(graph_distance, distance[i,:УзелНачала], distance[i,:УзелКонец], distance[i,:Расстояние])
end
# Если вместо расстояния поставить 1, то получим невзвешанный, неориентированный  граф
In [ ]: 
#Для примера, как вывести крайтчайшие расстояния
bb = dijkstra_shortest_paths(graph_distance, 1) # для примера, найдем крайтчайший путь от вершины 1 до всех вершин с помощью алгоритма Дийкстра
bb.dists # вывести крайтчайший расстояния от вершины 1 до всех вершин
Out[0]:
27-element Vector{Float64}:
    0.0
  268.0
  508.0
  601.0
 1116.0
 1252.0
  670.0
 1444.0
 2677.0
 2484.0
 2374.0
 2839.0
 1673.0
    ⋮
 1831.0
  938.0
 1254.0
 1124.0
  853.0
 1035.0
 1971.0
 2234.0
 2894.0
 1801.0
 1574.0
 1105.0

Найдем кратчайшие расстояния от каждой вершины ко всем вершинам с помощью алгоритма Дийкстра

In [ ]: 
# Найдем кратчайшие расстояния от каждой вершины ко всем вершинам с помощью алгоритма Дийкстра
masskm = [dijkstra_shortest_paths(graph_distance, y).dists for y in 1:n]

distance_count = zeros(n,n)
for i in 1:n
    for j in 1:n
        distance_count[i,j] = masskm[i][j]
    end
end
distance_count
Out[0]:
27×27 Matrix{Float64}:
    0.0   268.0   508.0   601.0  1116.0  …  2894.0  1801.0  1574.0  1105.0
  268.0     0.0   240.0   333.0   848.0     2626.0  1533.0  1306.0   837.0
  508.0   240.0     0.0   573.0   700.0     2478.0  1385.0  1158.0  1077.0
  601.0   333.0   573.0     0.0   515.0     2293.0  1200.0   973.0   504.0
 1116.0   848.0   700.0   515.0     0.0     1778.0   685.0   458.0   881.0
 1252.0   984.0   836.0   651.0   136.0  …  1914.0   549.0   594.0  1017.0
  670.0   402.0   642.0    69.0   446.0     2224.0  1131.0   904.0   435.0
 1444.0  1176.0  1028.0   843.0   328.0     1450.0   666.0   786.0  1209.0
 2677.0  2409.0  2261.0  2076.0  1561.0      217.0  1441.0  2019.0  2442.0
 2484.0  2216.0  2068.0  1883.0  1368.0      410.0  1248.0  1826.0  2249.0
 2374.0  2106.0  1958.0  1773.0  1258.0  …   520.0  1138.0  1716.0  2139.0
 2839.0  2571.0  2423.0  2238.0  1723.0       55.0  1603.0  2181.0  2604.0
 1673.0  1405.0  1257.0  1072.0   557.0     1221.0   437.0  1015.0  1438.0
    ⋮                                    ⋱                     ⋮    
 1831.0  1563.0  1415.0  1230.0   715.0  …  1063.0   595.0  1173.0  1596.0
  938.0   670.0   910.0   337.0   852.0     2630.0  1537.0  1310.0   417.0
 1254.0   986.0  1226.0   653.0  1168.0     2946.0  1853.0  1626.0   733.0
 1124.0   856.0  1096.0   523.0  1038.0     2816.0  1723.0  1496.0   603.0
  853.0   585.0   825.0   252.0   767.0     2545.0  1452.0  1225.0   332.0
 1035.0   767.0  1007.0   434.0   949.0  …  2727.0  1634.0  1407.0   514.0
 1971.0  1703.0  1555.0  1370.0   855.0     1519.0   339.0  1313.0  1736.0
 2234.0  1966.0  1818.0  1633.0  1118.0     1466.0   998.0  1576.0  1999.0
 2894.0  2626.0  2478.0  2293.0  1778.0        0.0  1658.0  2236.0  2659.0
 1801.0  1533.0  1385.0  1200.0   685.0     1658.0     0.0  1143.0  1566.0
 1574.0  1306.0  1158.0   973.0   458.0  …  2236.0  1143.0     0.0  1339.0
 1105.0   837.0  1077.0   504.0   881.0     2659.0  1566.0  1339.0     0.0

Запишем результат в файл Excel

In [ ]: 
#= 
Записывыает только результат в имеющийся файл result.xlsx, заранее подготовленный с листом "Количество_прыжков", 
где уже внесена таблица (шапочка). Файл должен быть закрыт в это время! Данные переносяться и сохраняются.
=#

XLSX.openxlsx("result.xlsx", mode="rw") do xf   # Редактирование существующего файла: режим "rw"
    sheet = xf["Кратчайшие_расстояния"]  # Обратиться к листу "Кратчайшие_расстояния" 
    sheet["D4:AD30"] = distance_count    # записать в ячейки D4:AD30 матрицу результатов
end;
In [ ]: 
# В результате получаем ответ в excel-файле
img = load( "$(@__DIR__)/pics/Result_Dijksta.jpg" )
Out[0]:
No description has been provided for this image

Сравним, есть ли разница между кратчайшими путями в "прыжках" и в"прыжках" по расстоянию

In [ ]: 
прыжки_1_5 = enumerate_paths(dijkstra_shortest_paths(graph_room, 1), 5) # "прыжки" по узлам в невзвешанном графе
Out[0]:
4-element Vector{Int64}:
 1
 2
 3
 5
In [ ]: 
расстояние_1_5 = enumerate_paths(dijkstra_shortest_paths(graph_distance, 1), 5) # "прыжки"по узлам в взвешанном графе
Out[0]:
5-element Vector{Int64}:
 1
 2
 4
 7
 5
In [ ]: 
прыжки_1_5 == расстояние_1_5 # сравниваем "прыжки" по узлам
Out[0]:
false

Заключение

Разница в количествах "прыжков" посещаемых вершин есть.Когда это может пригодиться?
Если бы вид транспорта на данной транспортной сети был бы настолько быстрый по скорости,
то для оптимизации времени в пути между узлами, вероятно, потребуется считать количество ребер,
так как расстояние между ними имеет гораздо меньшее значение, чем то, сколько прыжков потребуется (сколько узлов
придется посетить), чтобы добраться от одного узла до другого. Каждая станция может означать задержку,
поэтому, как и при полетах на самолете, чем меньше остановок, тем лучше
=#

Группа видимости
ПубличноПросматривать контент могут все пользователи сообщества

Тип

Проекты

Краткое описание

Создание графа на примере транспортной сети из матрицы смежности. Нахождение кратчайших путей в "прыжках" и расстояниях с помощью алгоритма Дийкстры

Связанные материалы

Пусто

Теги

Пусто

Категории

МероприятияЛетняя школа Julia
МероприятияКонкурс работ Engee 2024

Языки

    Julia

Форматы

    ngscript

Уровень

    Базовый

Статус

Опубликовано

Обновлено

Источник

Сообщество