How to write the Bellman-Ford algorithm in Python?

How to write the Bellman-Ford algorithm in Python?

The Bellman-Ford Algorithm is an algorithm for solving the single-source shortest path problem with negative-weighted edges. This article will introduce how to use Python to write the Bellman-Ford algorithm and provide specific code examples.

The core idea of ​​the Bellman-Ford algorithm is to optimize the path through step-by-step iteration until the shortest path is found. The steps of the algorithm are as follows:

1. Create an array dist[] to store the shortest distance from the source point to other vertices.
2. Initialize all elements of the dist[] array to infinity, but the distance from the source point is 0.
3. Through n-1 iterations, for each edge (u, v):
   1) If dist[v] > dist[u] weight(u, v), update dist[ v] is dist[u] weight(u, v).
4. Check whether there is a negative weight cycle. For each edge (u, v):
   1) If dist[v] > dist[u] weight(u, v), there is a negative weight cycle and the shortest path cannot be determined.
5. If there is no negative weight cycle, the shortest path has been calculated, and the dist[] array is the shortest path.

The following is a code example of the Bellman-Ford algorithm written in Python:

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    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("图中存在负权环，无法确定最短路径")
                return

        self.print_solution(dist)

    def print_solution(self, dist):
        print("顶点    最短距离")
        for i in range(self.V):
            print(i, "        ", dist[i])

# 示例用法
g = Graph(5)
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)
g.bellman_ford(0)

In the above example, a graph g is created and some edges are added. Then call the bellman_ford method to calculate the shortest path and print the result. In this example, the source point is 0 and the shortest path will be calculated.

The time complexity of the Bellman-Ford algorithm is O(V*E), where V is the number of vertices and E is the number of edges. In practical applications, if there is a negative weight cycle in the graph, the algorithm will not stop but will enter an infinite loop. Therefore, when using the Bellman-Ford algorithm, you should first check whether there is a negative weight cycle.

The above is the detailed content of How to write the Bellman-Ford algorithm in Python?. For more information, please follow other related articles on the PHP Chinese website!