Создаем функцию инициализации графа через матрицу смежности вершин и преобразуем в список ребер для оптимального использования алгоритма:

def get_adjacency_matrix():

    n = int(input("Введите количество вершин в графе: "))

    adj_matrix = []

    for i in range(n):

        row = list(map(int, input(f"Введите значения для вершины {i + 1}: ").split()))

        adj_matrix.append(row)

    edges = []

    for i in range(n):

        for j in range(n):

            if adj_matrix[i][j] != 0:

                edge = f"{i + 1}, {j + 1}, {adj_matrix[i][j]}"

                edges.append(edge)

    return edges

Данная функция запрашивает у пользователя размерность квадратной матрицы, построчно добавляет значения строки матрицы row в список adj_matrix. Далее матрица преобразуется в список ребер вида u, v, w, где w - значение веса ребра, инцидентного вершинам u и v.

Опишем функцию работы модифицированного алгоритма Беллмана-Форда:

from typing import List, Tuple, Union, Any

def bellman_ford_algorithm(edges: List[str], start_node: int, end_node: int) -> Union

[tuple[list[Any], list[Any]], tuple[list[int], list[float]]]:  

    inf = float("inf")

    n = len(edges)

    dist = [inf] * n

    prev = [-1] * n

    dist[start_node - 1] = 0

В данном элементе кода в функцию bellman_ford_algoritm инициализируем на вход следующие данные: стартовую вершину - start_node, конечную вершину - end_node, и список ребер - edges. Далее при помощи подключаемого модуля typing проверяем входные данные. Список edges должен иметь тип данных list, а стартовая и конечная вершины целочисленные значения int.

Переменная inf равна бесконечности и используется для инициализации списка dist, который содержит текущее кратчайшее расстояние от начальной вершины до каждой вершины в графе. Список prev инициализируется нулями и будет использоваться для хранения предыдущих вершин на кратчайшем пути.

Код последней строки dist[start_node - 1] = 0 устанавливает начальное расстояние до начального узла (список dist индексируется с 0, поэтому мы вычитаем 1 из start_node). Таким образом, мы можем начать поиск кратчайшего пути от начального узла и обновлять расстояние до остальных узлов по мере прохождения алгоритма Беллмана-Форда.

    for i in range(n - 1):

        for j in range(n):

            u, v, w = map(int, edges[j].split(","))

            if dist[u - 1] + w < dist[v - 1]:

                dist[v - 1] = dist[u - 1] + w

                prev[v - 1] = u - 1

Следующим шагом на каждой итерации алгоритма длины присвоим переменным u, v и w значения из списка edges при помощи оператора map, который позволяет присваивать переменным соответствующие входные значения, где u и v - номера вершин, соединенных ребром, а w - вес ребра. Инструкция for i in range(n-1) означает, что алгоритм будет проходить n-1 раз, так как кратчайший путь между двумя вершинами может содержать не более n-1 ребер. Инструкция for j in range(n) перебирает все ребра в графе на каждом шаге итерации.

Условие if dist[u - 1] + w < dist[v - 1] проверяет, можно ли улучшить текущий кратчайший путь от начальной вершины до вершины v через ребро (u, v) с учетом веса w. Если условие выполняется, то значения в массивах dist и prev обновляются, что дает новый кратчайший путь от начальной вершины до вершины v.

    for j in range(n):

        u, v, w = map(int, edges[j].split(","))

        if dist[u - 1] + w < dist[v - 1]:

            path = [end_node]

            node = prev[end_node - 1]

            while node != -1 and node not in path:

                path.append(node + 1)

                node = prev[node]

            path.append(node + 1)

            return list(reversed(path)), [dist[end_node-1]], True

    path = []

    node = end_node - 1

    while node != -1:

        path.append(node + 1)

        node = prev[node]

    return list(reversed(path)), [dist[end_node-1]], False

После того как все ребра в графе были рассмотрены, удостоверимся в отсутствии отрицательного цикла. Для этого снова проверяем список edges на наличие более короткого пути до вершины v, чем уже найденное значение в списке dist. Если такой путь существует, то функция возвращает в последнем значении True, которое используется для соответствующего сообщения о наличии отрицательного цикла. В ином случае функция в последнем значении возвращает False.

Независимо от наличия отрицательного цикла, функция возвращает список dist и отсортированный в обратном порядке список path, так как заполнение последнего списка было от конечной вершины к начальной.

def print_result(path: List[int], dist: List[int], k: bool):

    if not path:

        print("Невозможно найти путь между заданными вершинами.")

    elif k is True:

        print("В графе есть отрицательный цикл.")

    else:

        print(f"Длина кратчайшего пути: {dist[-1]}")

        print(f"Кратчайший путь: {' -> '.join(str(node) for node in path)}")

В последней функции опишем инструкцию для вывода полученного результата. В первую очередь проверим наличие пути между двумя заданными вершинами, и если он существует, то проверяется следующий блок elif, который сообщает о наличии отрицательного цикла, и если функция bellman_ford_algoritm вернула значение True в переменную k, то пользователь получит соответствующее сообщение. Последний блок else выполнится только при наличии маршрута между вершинами, тем самым вернет значения списков dist и path.

edges = get_adjacency_matrix()

start_node = int(input('Введите начальную вершину: '))

end_node = int(input('Введите конечную вершину: '))

path, dist, k = bellman_ford_algorithm(edges, start_node, end_node)

print_result(path, dist, k)

Завершающим этапом в переменные start_node и end_node запросим у пользователя стартовую и конечную вершины, далее последовательно вызовем вышеописанные функции.

2.6. Тестирование и отладка