如何用Python编写贝尔曼-福德算法？

如何用Python编写贝尔曼-福特算法？

贝尔曼-福特算法（Bellman-Ford Algorithm）是一种解决带有负权边的单源最短路径问题的算法。本文将介绍如何使用Python编写贝尔曼-福特算法，并提供具体代码示例。

贝尔曼-福特算法的核心思想是通过逐步迭代来优化路径，直到找到最短路径为止。算法的步骤如下：

1. 创建一个数组dist[]，存储从源点到其他顶点的最短距离。
2. 将dist[]数组的所有元素初始化为无穷大，但源点的距离为0。
3. 通过n-1次迭代，对于每条边(u, v)：
   1) 如果dist[v] > dist[u] + weight(u, v)，则更新dist[v]为dist[u] + weight(u, v)。
4. 检查是否存在负权环。对于每条边(u, v)：
   1) 如果dist[v] > dist[u] + weight(u, v)，则存在负权环，无法确定最短路径。
5. 如果不存在负权环，则最短路径已经被计算出来，dist[]数组即为最短路径。

以下是用Python编写的贝尔曼-福特算法的代码示例：

Vondy

下一代AI应用平台，汇集了一流的工具/应用程序

下载

立即学习“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)

以上示例中，创建了一个图g，并添加了一些边。接着调用bellman_ford方法来计算最短路径并打印结果。在这个示例中，源点是0，最短路径将被计算出来。

贝尔曼-福特算法的时间复杂度为O(V*E)，其中V是顶点数，E是边数。在实际应用中，如果图中存在负权环，算法将不会停止，而会进入无限循环。因此，在使用贝尔曼-福特算法时，应先检查是否存在负权环。