The Algorithms logo
The Algorithms
Acerca deDonar

Bellman Ford

p
P
from __future__ import annotations


def print_distance(distance: list[float], src):
    print(f"Vertex\tShortest Distance from vertex {src}")
    for i, d in enumerate(distance):
        print(f"{i}\t\t{d}")


def check_negative_cycle(
    graph: list[dict[str, int]], distance: list[float], edge_count: int
):
    for j in range(edge_count):
        u, v, w = (graph[j][k] for k in ["src", "dst", "weight"])
        if distance[u] != float("inf") and distance[u] + w < distance[v]:
            return True
    return False


def bellman_ford(
    graph: list[dict[str, int]], vertex_count: int, edge_count: int, src: int
) -> list[float]:
    """
    Returns shortest paths from a vertex src to all
    other vertices.
    >>> edges = [(2, 1, -10), (3, 2, 3), (0, 3, 5), (0, 1, 4)]
    >>> g = [{"src": s, "dst": d, "weight": w} for s, d, w in edges]
    >>> bellman_ford(g, 4, 4, 0)
    [0.0, -2.0, 8.0, 5.0]
    >>> g = [{"src": s, "dst": d, "weight": w} for s, d, w in edges + [(1, 3, 5)]]
    >>> bellman_ford(g, 4, 5, 0)
    Traceback (most recent call last):
     ...
    Exception: Negative cycle found
    """
    distance = [float("inf")] * vertex_count
    distance[src] = 0.0

    for _ in range(vertex_count - 1):
        for j in range(edge_count):
            u, v, w = (graph[j][k] for k in ["src", "dst", "weight"])

            if distance[u] != float("inf") and distance[u] + w < distance[v]:
                distance[v] = distance[u] + w

    negative_cycle_exists = check_negative_cycle(graph, distance, edge_count)
    if negative_cycle_exists:
        raise Exception("Negative cycle found")

    return distance


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    V = int(input("Enter number of vertices: ").strip())
    E = int(input("Enter number of edges: ").strip())

    graph: list[dict[str, int]] = [{} for _ in range(E)]

    for i in range(E):
        print("Edge ", i + 1)
        src, dest, weight = (
            int(x)
            for x in input("Enter source, destination, weight: ").strip().split(" ")
        )
        graph[i] = {"src": src, "dst": dest, "weight": weight}

    source = int(input("\nEnter shortest path source:").strip())
    shortest_distance = bellman_ford(graph, V, E, source)
    print_distance(shortest_distance, 0)
Acerca de este algoritmo

Declaración de problema

Dado un gráfico dirigido ponderado G(V,E) y un vértice de origen s ∈ V, determine para cada v v v ∈ V el trayecto más corto entre s y v.

Enfoque

  • Inicializar la distancia de la fuente a todos los vértices como infinito.
  • Inicializar la distancia a sí mismo como 0.
  • Crear una matriz dist[] de tamaño | V| con todos los valores como infinitos excepto dist[s].
  • Repita los siguientes |V| - 1 vez, dónde |V| es el número de vértices.
  • Crear otro bucle para ir a través de cada borde (u, v) en E y hacer lo siguiente:
    1. dist[v] = minimum(dist[v], dist[u] + peso de borde.
  • Por último, iterar a través de todos los bordes en la última vez, para asegurarse de que no hay ciclos ponderados negativamente.

Complejidad temporal

O(VE)

Complejidad espacial

O(V^2)

Nombre del Fundador

  • Richard Bellman & Lester Ford, Jr.

Ejemplo

# de vértices en el gráfico = 5 [A, B, C, D, E]
# de bordes en gráfico = 8

bordes [A->B, A->C, B->C, B->D, B->E, D->C, D->B, E->D]
peso [ -1, 4, 3, 2, 2, 5, 1, -4 ]
fuente [ A, A, B, B, B, D, D, E ]

borde A->B
graph->edge[0].src = A
graph->edge[0].dest = B
graph->edge[0].weight = -1

borde A->C
graph->edge[1] .src = A
graph->edge[1].dest = C
gráfico->edge[1] .weight = 4

borde B->C
graph->edge[2].src = B
graph->edge[2].dest = C
gráfico->edge[2].peso = 3

borde B->D
gráfico->edge[3] .src = B
graph->edge[3] .dest = D
gráfico->edge[3] .peso = 2

borde B->E
graph->edge[4].src = B
graph->edge[4].dest = E
gráfico->edge[4].peso = 2

borde D->C
graph->edge[5].src = D
graph->edge[5].dest = C
gráfico->edge[5].peso = 5

borde D->B
graph->edge[6] .src = D
graph->edge[6].dest = B
gráfico->edge[6].weight = 1

borde E->D
graph->edge[7] .src = E
graph->edge[7].dest = D
gráfico->edge[7].weight = -3

para la fuente = A

Distancia de vértice desde la fuente
A 0 A->A
B -1 A->B
C 2 A->B->C = -1 + 3
D -2 A->B->E->D = -1 + 2 + -3
E 1 A->B->E = -1 + 2

Enlaces de implementación de código

Explicación de vídeo

Un video explicando el algoritmo Bellman Ford

Otros

Fuentes utilizadas: