class Graph:
    def __init__(self, vertices):
        self.V = vertices  # Количество вершин
        self.edges = []  # Список рёбер

    # Добавление ребра в граф
    def add_edge(self, u, v, w):
        if w != 0:  # Добавляем только если вес не равен 0
            self.edges.append((u, v, w))

    # Алгоритм Беллмана-Форда
    def bellman_ford(self, src):
        # Инициализация
        self.dist = [float('inf')] * self.V
        self.pred = [None] * self.V
        self.dist[src] = 0

        # Шаги алгоритма
        for i in range(self.V - 1):
            print(f"\nИтерация {i + 1}:")
            for u, v, w in self.edges:
                if self.dist[u] != float('inf') and self.dist[u] + w < self.dist[v]:
                    # Обновляем расстояние до вершины v
                    self.dist[v] = self.dist[u] + w
                    # Обновляем предшественник для вершины v
                    self.pred[v] = u
            
            # Вывод текущих значений λ(v) и π(v)
            self.print_table()

        # Проверка на отрицательный цикл
        print("\nПроверка на отрицательный цикл:")
        negative_cycle = False
        for u, v, w in self.edges:
            if self.dist[u] != float('inf') and self.dist[u] + w < self.dist[v]:
                negative_cycle = True
                break
        
        if negative_cycle:
            print("Существует отрицательный цикл.")
        else:
            print("Отрицательных циклов не обнаружено.")
            self.print_result()

    def print_table(self):
        print(f"{'№':<12}{'λ(v)':<12}{'π(v)':<12}")
        for i in range(self.V):
            pred_str = self.pred[i] if self.pred[i] is not None else "N/A"
            print(f"{i:<12}{self.dist[i]:<12}{pred_str:<12}")

    def print_result(self):
        print("\nКратчайшие пути от источника:")
        for i in range(self.V):
            if self.dist[i] == float('inf'):
                print(f"Верша: {i}, Дист.: ∞, Путь: Нет")
            else:
                path = self.get_path(i)
                print(f"Верша: {i}, Дист.: {self.dist[i]}, Путь: {' -> '.join(map(str, path))}")

    def get_path(self, target):
        path = []
        while target is not None:
            path.append(target)
            target = self.pred[target]
        return path[::-1]  # Обратный порядок

# Функция для ввода матрицы смежности от пользователя
def input_adjacency_matrix():
    V = int(input("Введите количество вершин в графе: "))
    print("Введите матрицу смежности (через запятую, используйте '0' для отсутствующих рёбер):")
    matrix = []
    for i in range(V):
        row = input(f"Введите строку {i + 1}: ").split(',')
        row = [0 if x.strip() == '0' else int(x.strip()) for x in row]
        matrix.append(row)
    return V, matrix

# Основная часть программы
if __name__ == "__main__":
    V, adjacency_matrix = input_adjacency_matrix()
    g = Graph(V)

    # Заполнение рёбер на основе матрицы смежности
    for i in range(V):
        for j in range(V):
            if adjacency_matrix[i][j] != 0 and i != j:  # Если вес не 0, добавляем ребро
                g.add_edge(i, j, adjacency_matrix[i][j])

    g.bellman_ford(0)
Программа должна выводить табличку в виде: №Итерации|Лямбда(1)/пи(1)|...|Лямбда(кол-во ребер)/Пи(кол-во ребер)