Detailed explanation of Bellman Ford algorithm and implementation in Python

Bellman Ford algorithm (Bellman Ford) can find the shortest path from the target node to other nodes in the weighted graph. This is very similar to the Dijkstra algorithm. The Bellman-Ford algorithm can handle graphs with negative weights and is relatively simple in terms of implementation.

Detailed explanation of the principle of Bellman Ford algorithm

The Bellman Ford algorithm iteratively finds new paths shorter than the overestimated paths by overestimating the path lengths from the starting vertex to all other vertices.

Because we want to record the path distance of each node, we can store it in an array of size n, n also represents the number of nodes.

Instance diagram

#1. Select the starting node, assign it to all other vertices infinitely, and record the path value.

2. Visit each edge and perform a relaxation operation to continuously update the shortest path.

3. We need to do this N-1 times, because in the worst case, the shortest node path length may need to be readjusted N- 1 time.

4. Notice how the node in the upper right corner adjusts its path length.

5. After all nodes have path lengths, check whether there is a negative loop.

Python implements Bellman Ford algorithm

class Graph:

    def __init__(self, vertices):
        self.V = vertices   # Total number of vertices in the graph
        self.graph = []     # Array of edges

    def add_edge(self, s, d, w):
        self.graph.append([s, d, w])

    def print_solution(self, dist):
        print("Vertex Distance from Source")
        for i in range(self.V):
            print("{0}\t\t{1}".format(i, dist[i]))

    def bellman_ford(self, src):

        dist = [float("Inf")] * self.V
        dist[src] = 0

        for _ in range(self.V - 1):
            for s, d, w in self.graph:
                if dist[s] != float("Inf") and dist[s] + w < dist[d]:
                    dist[d] = dist[s] + w

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

        self.print_solution(dist)

g = Graph(5)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 4)
g.add_edge(1, 3, 3)
g.add_edge(2, 1, 6)
g.add_edge(3, 2, 2)

g.bellman_ford(0)

The above is the detailed content of Detailed explanation of Bellman Ford algorithm and implementation in Python. For more information, please follow other related articles on the PHP Chinese website!