How can I implement the Bellman-Ford algorithm in Python?

How can I implement the Bellman-Ford algorithm in Python?

The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph. Would you like a code example?

Yes, please provide a code example.

Here's a simple implementation:

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # No. of vertices
        self.graph = []  # default dictionary

    def add_edge(self, u, v, w):
        self.graph.append((u, v, w))

    def bellman_ford(self, src):
        dist = [float('inf')] * self.V
        dist[src] = 0

        for _ in range(self.V - 1):
            for u, v, w in self.graph:
                if dist[u] != float('inf') and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        for u, v, w in self.graph:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                print("Graph contains negative weight cycle")
                return

        return dist

Would you like to know how to use this code?

Yes, how do I use this code to find the shortest path?

To use the code, create a graph instance, add edges, and call the bellman_ford method. Here's an example:

# Create a graph with 5 vertices
g = Graph(5)
# Add edges (u, v, weight)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)

# Find shortest paths from vertex 0
print(g.bellman_ford(0))

This will print the shortest distances from the source vertex 0 to all other vertices.