KAN`ский блог Мысли вслух…
  • Июн
    15

    Реализация Алгоритма Беллмана-Форда на python

    Алгоритм Беllman-Форда (Bellman-Ford algorithm) — это алгоритм для поиска кратчайших путей в графе, который может обрабатывать отрицательные веса ребер.

    class Graph:
        def __init__(self):
            self.edges = []
            self.vertices = set()
    
        def add_edge(self, u, v, weight):
            self.edges.append((u, v, weight))
            self.vertices.add(u)
            self.vertices.add(v)
    
        def get_edges(self):
            return self.edges
        
        def get_vertices(self):
            return self.vertices
    
    def bellman_ford(graph, start):
        distances = {v: float('infinity') for v in graph.get_vertices()}
        distances[start] = 0
    
        for _ in range(len(graph.get_vertices()) - 1):
            for u, v, weight in graph.get_edges():
                if distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight
    
        for u, v, weight in graph.get_edges():
            if distances[u] + weight < distances[v]:
                raise ValueError("Graph contains a negative cycle")
    
        return distances
    
     # Example usage:
    graph = Graph()
    graph.add_edge('A', 'B', 1)
    graph.add_edge('A', 'C', 4)
    graph.add_edge('B', 'C', 2)
    graph.add_edge('B', 'D', 5)
    graph.add_edge('D', 'E', -3)
    
    for u, v, weight in graph.get_edges():
        print(f"Edge from {u} to {v} with weight {weight}")
    
    start_vertex = 'A'
    distances = bellman_ford(graph, start_vertex)
    print(distances)  # Output: {'A': 0, 'B': 1, 'C': 3, 'D': -2, 'E': -5}
    

    В этом примере, `graph` — это граф, который представлен в виде словаря, где ключ — имя вершины, значение — список ребер, исходящих из этой вершины. `edges()` — это метод, возвращающий все ребра графа.

    Алгоритм Bellman-Форда выполняет |V| — 1 проходов по всем ребрам, где |V| — количество вершин в графе. В каждую из этих проходов, он обновляет расстояние до всех вершин, которые могут быть достигнуты из исходной вершины с помощью ребер, которые были обновлены на предыдущем проходе.

    После |V| — 1 проходов, алгоритм может определить, есть ли в графе отрицательный цикл. Если найден отрицательный цикл, то выбрасывается исключение `ValueError`.

    В `distances` — это словарь, который хранит расстояния до всех вершин, которые могут быть достигнуты из исходной вершины.

    No Comments

Comments are closed.