Bellman-Ford算法的原理与实现

Bellman-Ford算法是一种用于解决带有负权边的最短路径问题的算法。与Dijkstra算法不同，Bellman-Ford算法可以处理负权边，因此更加通用。

算法原理：

1. 创建一个距离数组dist，用于存储从源节点到其它节点的最短距离。将源节点的距离初始化为0，其它节点的距离初始化为无穷大。

2. 对于图中的每一条边(u, v, w)，循环遍历，将通过中间节点u到达节点v的距离更新为dist[v] = min(dist[v], dist[u]+w)。其中w为u到v的边的权重。

3. 重复上述步骤，直到没有边需要更新距离或者进行n-1次迭代（n为节点数量）。

4. 最后检查是否存在负环路。如果在第n次迭代后，还存在边可以更新距离，说明存在负环路。这是因为一个图的最短路径最多只能经过n-1条边，如果存在n条边进行距离更新，则说明存在负环路。

算法实现：

import sys

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 print_solution(self, dist):
        print("Vertex Distance from Source")
        for i in range(self.V):
            print(f"{i}\t\t{dist[i]}")
    
    def bellman_ford(self, src):
        dist = [float("Inf")] * self.V
        dist[src] = 0
        
        # Relax all edges |V| - 1 times
        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
        
        # Check for negative-weight cycles
        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
        
        self.print_solution(dist)

使用例子：

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)

输出结果：

Vertex Distance from Source
0		0
1		-1
2		2
3		-2
4		1

上述例子中，我们创建了一个包含5个节点的图。通过调用add_edge方法添加边。最后通过调用bellman_ford方法计算从源节点0到其它节点的最短距离。在输出结果中，每一行表示从源节点到对应节点的最短距离。

Bellman-Ford算法时间复杂度为O(V*E)，其中V为节点数量，E为边数量。