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)Программа не работает какнадо
- Assistant
Чтобы исправить вашу программу и убедиться в её правильной работе, я внесу несколько комментариев и проверю, где могут возникнуть проблемы.
Что может быть не так:
-
Ошибка обработки входных данных:
- Вы неправильно обрабатываете нулевые значения в матрице смежности и для некоторых графов с нулевыми весами ребер это поведение не соответствует требованиям алгоритма. Вы рассматривали
0как отсутствие ребра, но иногда вес ребра может быть равен 0.
- Вы неправильно обрабатываете нулевые значения в матрице смежности и для некоторых графов с нулевыми весами ребер это поведение не соответствует требованиям алгоритма. Вы рассматривали
-
Форматирующий вывод: В процессе работы Bellman-Форда вывод таблицы может не оказывать влияния на сам функционал, но это может нагружать процесс.
-
Логика проверки отрицательных циклов: Логика проверки отрицательных циклов отрабатывает правильно, но горуже она неоченььте пасет звыов.
-
**Обработка цикла ввода недостат этоитератор перехожет **
Давайте разберем и и наложим чтение корректировки !!!= ..
-