#### Bellman Ford

G
S
G
K
A
I
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)
```

#### Problem Statement

Given a weighted directed graph G(V,E) and a source vertex s ∈ V, determine for each vertex v ∈ V the shortest path between s and v.

#### Approach

• Initialize the distance from the source to all vertices as infinite.
• Initialize the distance to itself as 0.
• Create an array dist[] of size |V| with all values as infinite except dist[s].
• Repeat the following |V| - 1 times. Where |V| is number of vertices.
• Create another loop to go through each edge (u, v) in E and do the following:
1. dist[v] = minimum(dist[v], dist[u] + weight of edge).
• Lastly iterate through all edges on last time to make sure there are no negatively weighted cycles.

O(VE)

O(V^2)

#### Founder's Name

• Richard Bellman & Lester Ford, Jr.

#### Example

``````    # of vertices in graph = 5 [A, B, C, D, E]
# of edges in graph = 8

edges  [A->B, A->C, B->C, B->D, B->E, D->C, D->B, E->D]
weight [ -1,    4,    3,    2,    2,    5,    1,   -4 ]
source [  A,    A,    B,    B,    B,    D,    D,    E ]

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

// edge A->C
graph->edge[1].src = A
graph->edge[1].dest = C
graph->edge[1].weight = 4

// edge B->C
graph->edge[2].src = B
graph->edge[2].dest = C
graph->edge[2].weight = 3

// edge B->D
graph->edge[3].src = B
graph->edge[3].dest = D
graph->edge[3].weight = 2

// edge B->E
graph->edge[4].src = B
graph->edge[4].dest = E
graph->edge[4].weight = 2

// edge D->C
graph->edge[5].src = D
graph->edge[5].dest = C
graph->edge[5].weight = 5

// edge D->B
graph->edge[6].src = D
graph->edge[6].dest = B
graph->edge[6].weight = 1

// edge E->D
graph->edge[7].src = E
graph->edge[7].dest = D
graph->edge[7].weight = -3

for source = A

Vertex   Distance from Source
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
``````

#### Video Explanation

A video explaining the Bellman-Ford Algorithm

Sources Used: