贝尔曼-福特算法（Bellman-Ford Algorithm）是一种用于解决图中单源最短路径问题的算法，它可以处理包含负权边的图。该算法通过对图中的所有边进行松弛操作，逐步逼近最短路径。

基本介绍

算法步骤：

1. 初始化：将源节点的距离设置为0，其他节点的距离设置为无穷大。

2. 重复以下步骤（节点数量-1）次：

   • 对图中的每条边进行松弛操作。如果通过当前边可以获得更短的路径，则更新目标节点的距离。

3. 检查是否存在负权回路。如果在第（节点数量-1）次松弛操作后仍然存在节点的距离可以被更新，则说明存在负权回路。

使用场景：

• 贝尔曼-福特算法可以处理包含负权边的图，而Dijkstra算法不能处理负权边的情况。
• 该算法适用于解决单源最短路径问题，并且可以应用于有向图或无向图。

使用举例

下面的有向图 G 中包含 5 个顶点和 8 条边。假设源点 为 A。初始化 distSet 所有距离为 INFI，源点 A 为 0。

由于图中有 5 个顶点，按照步骤 1 需要遍历 4 次，第一次遍历的结果如下。

第二次遍历的结果如下。

以此类推可以得出完全遍历的结果。

基于JAVA代码

class Edge {
    int source, destination, weight;

    public Edge(int source, int destination, int weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }
}

class BellmanFordAlgorithm {
    private int vertices, edges;
    private List<Edge> edgeList;

    public BellmanFordAlgorithm(int vertices, int edges) {
        this.vertices = vertices;
        this.edges = edges;
        edgeList = new ArrayList<>();
    }

    public void addEdge(int source, int destination, int weight) {
        Edge edge = new Edge(source, destination, weight);
        edgeList.add(edge);
    }

    public void shortestPath(int source) {
        int[] distances = new int[vertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;

        for (int i = 1; i < vertices; ++i) {
            for (Edge edge : edgeList) {
                int u = edge.source;
                int v = edge.destination;
                int weight = edge.weight;
                if (distances[u] != Integer.MAX_VALUE && distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                }
            }
        }

        // 检查负权回路
        for (Edge edge : edgeList) {
            int u = edge.source;
            int v = edge.destination;
            int weight = edge.weight;
            if (distances[u] != Integer.MAX_VALUE && distances[u] + weight < distances[v]) {
                System.out.println("图中存在负权回路");
                return;
            }
        }

        // 打印最短路径
        for (int i = 0; i < vertices; ++i) {
            System.out.println("从源节点 " + source + " 到节点 " + i + " 的最短路径距离为: " + distances[i]);
        }
    }

    public static void main(String[] args) {
        int vertices = 5;
        int edges = 8;
        BellmanFordAlgorithm algorithm = new BellmanFordAlgorithm(vertices, edges);

        algorithm.addEdge(0, 1, 4);
        algorithm.addEdge(0, 2, 1);
        algorithm.addEdge(1, 3, 1);
        algorithm.addEdge(2, 1, -2);
        algorithm.addEdge(2, 3, 6);
        algorithm.addEdge(3, 4, 3);
        algorithm.addEdge(4, 3, -2);
        algorithm.addEdge(4, 2, 2);

        int source = 0;
        algorithm.shortestPath(source);
    }
}

参考 1.Bellman-Ford 单源最短路径算法 2.贝尔曼-福特算法