4. Алгоритм Беллмана-Форда [Электронный ресурс] режим доступа URL: https://habr.com/ru/companies/otus/articles/484382/ (дата обращения: 20.04.2023)

5. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. / М.: Издательский дом «Вильямс», 2011.-- 1296 с. (дата обращения: 30.04.2023)

Приложение А

Приложение Б

from typing import List, Tuple, Union, Any

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

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

    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

    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]:

                return [], []

    path = []

    node = end_node - 1

    while node != -1:

        path.append(node + 1)

        node = prev[node]

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

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

    if not path and not dist:

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

    elif not path:

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

    else:

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

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