Макросы для Excel: Как использовать алгоритм Флойда для нахождения кратчайшего пути
Макросы в Excel - это мощный инструмент, который позволяет автоматизировать повторяющиеся задачи и упростить работу с данными. Один из популярных алгоритмов, который можно использовать с помощью макросов, это алгоритм Флойда. Этот алгоритм позволяет найти кратчайший путь между всеми парами вершин в графе.
Для использования алгоритма Флойда с помощью макросов в Excel, вам понадобится следующий код:
Sub FloydAlgorithmWithFullRange()
Dim i As Integer, j As Integer, k As Integer
Dim n As Integer
Dim inputRange As Range
Set inputRange = Application.InputBox("Выберите диапазон ячеек с матрицей", Type:=8)
n = Sqr(inputRange.Cells.Count) ' Получаем размерность матрицы
Dim matrix() As Variant
ReDim matrix(1 To n, 1 To n)
'Заполнение матрицы значениями из выбранного диапазона
Dim count As Integer
count = 1
For i = 1 To n
For j = 1 To n
matrix(i, j) = inputRange.Cells(count).Value
If i = j Then
matrix(i, j) = 0
ElseIf matrix(i, j) = "" Then
matrix(i, j) = 9999 'Значение "бесконечность"
End If
count = count + 1
Next j
Next i
'Алгоритм Флойда
For k = 1 To n
For i = 1 To n
For j = 1 To n
If matrix(i, k) + matrix(k, j) < matrix(i, j) Then
matrix(i, j) = matrix(i, k) + matrix(k, j)
End If
Next j
Next i
Next k
'Вывод результата в другой выбранный диапазон
Dim outputRange As Range
Set outputRange = Application.InputBox("Выберите верхнюю левую ячейку для вывода результата", Type:=8)
For i = 1 To n
For j = 1 To n
outputRange.Offset(i - 1, j - 1).Value = matrix(i, j)
Next j
Next i
End Sub
Если вы хотите, чтобы этот код выводил не расстояние между вершинами, а наикратчайшее количество ходов, вам нужно внести некоторые изменения в алгоритм. Вместо того, чтобы просто суммировать значения в матрице, вы можете добавить счетчик, который будет отслеживать количество шагов от одной вершины к другой.
Для этого вам нужно добавить дополнительную переменную, которая будет хранить количество шагов, и изменить условие внутреннего цикла алгоритма Флойда. Вот как это можно сделать:
'Алгоритм Флойда для нахождения кратчайшего количества шагов
For k = 1 To n
For i = 1 To n
For j = 1 To n
If matrix(i, k) + matrix(k, j) < matrix(i, j) Then
matrix(i, j) = matrix(i, k) + matrix(k, j)
'Добавляем шаг к количеству шагов
steps(i, j) = steps(i, k) + steps(k, j)
End If
Next j
Next i
Next k
Таким образом, вы можете использовать алгоритм Флойда с макросами в Excel для нахождения кратчайшего пути или количества шагов между вершинами в графе. Надеемся, что эта информация будет полезной для вас при работе с данными в Excel.
Комментарии