class Graph: def init(self, vertices): self.V = vertices # Количество вершин self.edges…
- User
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)|...|Лямбда(кол-во ребер)/Пи(кол-во ребер)
- Assistant
Программа, как представлена, выводит результаты выполнения алгоритма Беллмана-Форда в удобной таблице. Чтобы реализовать вывод в формате, который вы хотите, с включением номера итерации в заголовок и состава таблицы в виде
λ(v)/π(v)для каждого узла, необходимо слегка модернизировать код методаprint_table. Ниже приведён весь обновлённый код программы с модификациями для требуемого вывода.
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 iteration in range(self.V - 1): print(f"\n{'#' * 10} Итерация {iteration + 1} {'#' * 10}") updated = False 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 updated = True # Вывод текущих значений λ(v) и π(v) self.print_table(iteration + 1) if not updated: print("На данной итерации обновлений не было, работа алгоритма окончена.") break # Проверка на отрицательный цикл 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, iteration): # Шапка таблицы print(f"\n## Таблица итерации {iteration} ##") header = f"{'№':<5}" + ''.join([f"λ({v + 1})/π({v + 1}):<15" for v in range(self.V)]) print(header) print('-' * len(header)) # Печать значений λ(v) и π(v) row = " | ".join(f"{self.dist[v] if self.dist[v] != float('inf') else '∞'}/{str(self.pred[v] + 1) if self.pred[v] is not None else 'N/A'}" for v in range(self.V)) print(f"{iteration:<5}{row}") def print_result(self): print("\nКратчайшие пути от источника:") for i in range(self.V): if self.dist[i] == float('inf'): print(f"Вершина: {i + 1}, Дистанция: ∞, Путь: Нет") else: path = self.get_path(i) print(f"Вершина: {i + 1}, Дистанция: {self.dist[i]}, Путь: {' -> '.join(map(str, [p + 1 for p in 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)
Изменения в коде:
-
Функция
print_tableбыла модифицирована:- Добавлен заголовок и формат
λ(v)/π(v)для каждой вершины. - Вывод координирован так, чтобы каждая вершина и её значения для
λ(v)иπ(v)выводились в строке.
- Добавлен заголовок и формат
-
Базовые улучшения в логике цикла:
- Реализована проверка на отсутствие обновлений при итерации. Если ни одно значение не было обновлено, программа завершает цикл итераций до проверки на отрицательные циклы.
- Корректно выводится информация в табличной форме.
-
Нумерация вершин:
- Все вершины пронумерованы с 1 для улучшения понимания.
Пример работы:
Для следующей матрицы смежности ввода:
0,6,0,7 0,0,5,8 0,-2,0,0 0,0,-3,0Результат (для вершины источника
0) должен будет выглядеть так на первой итерации (табличный вывод):## Таблица итерации 1 ## № λ(1)/π(1): λ(2)/π(2): λ(3)/π(3): λ(4)/π(4): 0 0/N/A 6/1 ∞/N/A 7/1На последующих итерациях таблицы будут обновляться в зависимости от выполнения алгоритма.
-