Блог думающего студента

Описание вашего блога

Макросы для 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.