有权最短路径问题：贝文曼福德(Bellman Ford)算法 & Java 实现

一、贝尔曼福德算法

1. 简介

贝尔曼福德（Bellman Ford）算法也是求解单源最短路径问题，相比狄克斯特拉（dijkstra）算法，它运行效率会差一些，但是它可以处理边的权重为负值的情况，而狄克斯特拉算法要求变的权重不能为负数。

备注： 狄克斯特拉算法，可以戳这个链接：https://blog.csdn.net/afei__/article/details/83352205

2. 算法思想

松弛操作指针对边（u，v），如果 v.distance > u.distance + weight，则更新 v.distance 的值。 贝尔曼福德算法通过对边进行松弛操作来渐近地降低每个顶点到起始点的距离。 当存在权重为负值的环路时，算法返回 False，表示不存在解决方案（因为我们可以在权重为负的环路上无限循环，使得距离变成负无穷大）。 当不存在权重为负值的环路时，算法返回 True，并给出每个顶点到起始点的最短距离。

3. 图解过程

图中是我们对每条边进行松弛操作的过程，阴影边表示前驱值。我们可以证明当不存在权重为负数的环路时，对每条边循环执行 V - 1 次松弛操作后，每个顶点的距离将就是最短距离（证明过程这里不给了，在《算法导论》相关章节中有，我们记住结论就行）。

二、代码实现

1. Edge 类

由于该算法中需要经常对边进行操作，所以我们还是把边写为一个具体的类，方便操作。

public class Edge { private Vertex start; private Vertex end; private int weight; // 权重（边的长度） public Edge(Vertex start, Vertex end, int weight) { this.start = start; this.end = end; this.weight = weight; } public Vertex getStart() { return start; } public Vertex getEnd() { return end; } public int getWeight() { return weight; } }

2. Vertex 类

这里我们使用 Edge 类的一个集合来表示该顶点可以到达的邻居顶点。

import java.util.LinkedList; public class Vertex { private char id; // 顶点的标识 private LinkedList<Edge> edges; // 当前顶点可直接达到的边 private Vertex parent; // 上一个顶点是谁(前驱)，用来记录路径的 private int distance = Integer.MAX_VALUE; // 距离起始点的距离 public Vertex(char id) { this.id = id; this.edges = new LinkedList<>(); } public char getId() { return id; } public LinkedList<Edge> getNeighbors() { return edges; } public void addNeighbor(Vertex vertex, int weight) { edges.add(new Edge(this, vertex, weight)); // 起点均是当前顶点 } public Vertex getParent() { return parent; } public void setParent(Vertex parent) { this.parent = parent; } public int getDistance() { return distance; } public void setDistance(int distance) { this.distance = distance; } @Override public String toString() { return String.format("Vertex[%c]: distance is %d , predecessor is '%s'", id, distance, parent == null ? "null" : parent.id); } }

3. 场景类

说明看代码注释吧，注释应该写的比较清楚了。

import java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { List<Vertex> list = getTestData(); // 设置第0个顶点为起始点 Vertex source = list.get(0); source.setDistance(0); // 贝文曼福德算法 boolean flag = bellmanFord(list, source); // 打印结果 System.out.println("是否存在解决方案：" + flag); for (int i = 0; i < list.size(); i++) { Vertex vertex = list.get(i); System.out.println(vertex.toString()); } } public static boolean bellmanFord(List<Vertex> list, Vertex source) { // 1. 将所有边添加到一个队列中 LinkedList<Edge> queue = new LinkedList<>(); for (int i = 0; i < list.size(); i++) { queue.addAll(list.get(i).getNeighbors()); } // 2. 需要执行 (V-1)*E 次松弛操作 for (int i = 1; i < list.size(); i++) { for (Edge edge : queue) { relax(edge); } } // 3. 验证是否存在权重为负数的环路 for (Edge edge : queue) { Vertex u = edge.getStart(); Vertex v = edge.getEnd(); // 对于边 (u, v)，如果 v.distance > u.distance + weight，则说明是负数环路 if (v.getDistance() > u.getDistance() + edge.getWeight()) { return false; } } return true; } public static void relax(Edge edge) { Vertex start = edge.getStart(); Vertex end = edge.getEnd(); int distance = start.getDistance() + edge.getWeight(); if (end.getDistance() > distance) { end.setDistance(distance); end.setParent(start); } } public static List<Vertex> getTestData() { Vertex s = new Vertex('s'); Vertex t = new Vertex('t'); Vertex x = new Vertex('x'); Vertex y = new Vertex('y'); Vertex z = new Vertex('z'); s.addNeighbor(t, 6); // s->t : 6 s.addNeighbor(y, 7); // s->y : 7 t.addNeighbor(x, 5); // t->x : 5 t.addNeighbor(y, 8); // t->y : 8 t.addNeighbor(z, -4); // t->z : -4 x.addNeighbor(t, -2); // x->t : -2 y.addNeighbor(x, -3); // y->x : -3 y.addNeighbor(z, 9); // y->z : 9 z.addNeighbor(s, 2); // z->s : 2 z.addNeighbor(x, 7); // z->x : 7 LinkedList<Vertex> list = new LinkedList<>(); list.add(s); list.add(t); list.add(x); list.add(y); list.add(z); return list; } }

4. 执行结果

是否存在解决方案：true Vertex[s]: distance is 0 , predecessor is 'null' Vertex[t]: distance is 2 , predecessor is 'x' Vertex[x]: distance is 4 , predecessor is 'y' Vertex[y]: distance is 7 , predecessor is 's' Vertex[z]: distance is -2 , predecessor is 't'

对应下图，由于本例中没有权重为负数的环路，所有存在解决方案，且每个顶点的最短距离结果也正确。