Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-2024-11-20· OpenAIAi2 WildChat-4.8M (AI2)

class Graph: def init(self, vertices): self.V = vertices # Количество вершин self.edges…

  1. 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)
    

    Программа не работает какнадо

  2. Assistant

    Чтобы исправить вашу программу и убедиться в её правильной работе, я внесу несколько комментариев и проверю, где могут возникнуть проблемы.

    Что может быть не так:

    1. Ошибка обработки входных данных:

      • Вы неправильно обрабатываете нулевые значения в матрице смежности и для некоторых графов с нулевыми весами ребер это поведение не соответствует требованиям алгоритма. Вы рассматривали 0 как отсутствие ребра, но иногда вес ребра может быть равен 0.
    2. Форматирующий вывод: В процессе работы Bellman-Форда вывод таблицы может не оказывать влияния на сам функционал, но это может нагружать процесс.

    3. Логика проверки отрицательных циклов: Логика проверки отрицательных циклов отрабатывает правильно, но горуже она неоченььте пасет звыов.

    4. **Обработка цикла ввода недостат этоитератор перехожет **

    Давайте разберем и и наложим чтение корректировки !!!= ..