寻找有向负权环

判断有向环的实现并不复杂&＃xff0c;核心思想其实是DFS&＃xff08;深度优先搜索&＃xff09;。

package Chap7;import java.util.LinkedList;public class NegativeDiCycle {private boolean[] marked;private DiEdge[] edgeTo;private boolean[] onStack;private LinkedList cycle;public NegativeDiCycle(EdgeWeightedDiGraph graph) {marked &＃61; new boolean[graph.vertexNum()];edgeTo &＃61; new DiEdge[graph.vertexNum()];onStack &＃61; new boolean[graph.vertexNum()];// 有向图可能不是强连通的&＃xff0c;所以需要从每个顶点出发&＃xff0c;寻找负权环for (int i &＃61; 0; i graph, int v) {// 模拟系统递归使用的栈&＃xff0c;方法开始进栈&＃xff1b;方法结束出栈onStack[v] &＃61; true;marked[v] &＃61; true;for (DiEdge edge : graph.adj(v)) {// 如果已经存在负权回路&＃xff0c;终止递归方法if (this.hasNegativeDiCycle()) {return;}int w &＃61; edge.to();if (!marked[w]) {edgeTo[w] &＃61; edge;dfs(graph, w);// v -> w的路径&＃xff0c;且w在栈中&＃xff0c;说明形成有向环} else if (onStack[w]) {cycle &＃61; new LinkedList<>();DiEdge e &＃61; edgeTo[v];while (e.from() !&＃61; w) {cycle.push(e);e &＃61; edgeTo[e.from()];}// 为避免空指针&＃xff0c;离w最近的那条在循环外入栈cycle.push(e);// 把导致成环的边加入cycle.push(edge);}}onStack[v] &＃61; false;}public boolean hasNegativeDiCycle() {if (cycle !&＃61; null) {double cycleWeight &＃61; cycle.stream().mapToDouble(DiEdge::weight).sum();if (cycleWeight <0) {return true;}}return false;}public Iterable cycle() {if (hasNegativeDiCycle()) {return cycle;}return null;}}

使用DFS的原因主要是为了利用递归产生的由系统维护的栈&＃xff08;每次方法调用就相当于入栈&＃xff0c;最先调用的最后才返回&＃xff09;&＃xff0c;而递归方法dfs的调用顺序正好反映了顶点的访问顺序&＃xff0c;如先调用dfs(s)&＃xff0c; 接着dfs(w), 然后dfs(x)&＃xff0c;再递归调用dfs(v)&＃xff0c;那么这是一条s -> w -> x -> v的路径。我们使用了一个onStack[]布尔数组来模拟方法调用的进出栈情况——进入方法体说明方法被调用&＃xff0c;进栈&＃xff1b;方法执行完毕&＃xff0c;该返回到上一层方法调用中了&＃xff0c;出栈。onStack[]其实就是一条路径&＃xff0c;onStack[v] &＃61; true说明顶点v位于从起点s可达的onStack[]这条路径中。

该实现最为关键的就是理解&＃xff1a;当我们在v处发现某条v -> w的边&＃xff0c;而恰好其w位于onStack[]中&＃xff0c;就找到了一个环。我们知道onStack[]表示的是s -> w -> x -> v的路径&＃xff0c;现在v -> w 刚好补全w -> x -> v成为环&＃xff01;如下图所示

好&＃xff0c;寻找到有向环后&＃xff0c;再判断环内所有边的权值是不是负数就好了。该实现不仅能判断&＃xff0c;还能找出到底是哪些边造成了环。关键是以下几行

DiEdge e &＃61; edgeTo[v];
while (e.from() !&＃61; w) {cycle.push(e);e &＃61; edgeTo[e.from()];
}
// 为避免空指针&＃xff0c;离w最近的那条在循环外入栈
cycle.push(e);
// 把导致成环的边加入
cycle.push(edge);

对照着上图&＃xff0c;最先x -> v入栈&＃xff0c;到w -> x时候&＃xff0c;发现e.from()就是w&＃xff0c;不存入。出了while循环&＃xff0c;将这条w -> x入栈&＃xff0c;最后别忘了把导致成环的那条边入栈。有人可能会说了为何要这么麻烦&＃xff0c;循环外单独push了两次&＃xff0c;这是因为edgeTo[]中有的值是null&＃xff08;比如起点s&＃xff09;&＃xff0c;如果不在合适的地方终止循环&＃xff0c;将在e &＃61; edgeTo[e.from()]该语句执行后&＃xff0c;在e.from() !&＃61; w处引起空指针异常&＃xff01;

SPFA算法的实现

可以判断负权回路的是否存在了&＃xff0c;据此实现SPFA算法。

package Chap7;import java.util.*;public class SPFA {private double[] distTo;private DiEdge[] edgeTo;private Queue queue;private boolean[] onPQ; // 顶点是否在queue中private int cost; // 记录放松了边的次数private Iterable cycle; // 找到的负权回路public boolean hasNegativeCycle() {return cycle !&＃61; null;}private void findNegativeCycle() {EdgeWeightedDiGraph g &＃61; new EdgeWeightedDiGraph<>(edgeTo.length);for (int v &＃61; 0; v graph, int v) {for (DiEdge edge : graph.adj(v)) {int w &＃61; edge.to();if (distTo[v] &＃43; edge.weight() graph, int s) {distTo &＃61; new double[graph.vertexNum()];edgeTo &＃61; new DiEdge[graph.vertexNum()];queue &＃61; new LinkedList<>();onPQ &＃61; new boolean[graph.vertexNum()];for (int i &＃61; 0; i cycle() {return cycle;}public double distTo(int v) {return distTo[v];}public boolean hasPathTo(int v) {return distTo[v] !&＃61; Double.POSITIVE_INFINITY;}public Iterable pathTo(int v) {if (hasPathTo(v)) {LinkedList path &＃61; new LinkedList<>();for (DiEdge edge &＃61; edgeTo[v]; edge !&＃61; null; edge &＃61; edgeTo[edge.from()]) {path.push(edge);}return path;}return null;}public static void main(String[] args) {List vertexInfo &＃61; List.of("v0", "v1", "v2", "v3");int[][] edges &＃61; {{0, 1}, {1, 2}, {2, 0}, {0, 3}, {2, 3}};double[] weight &＃61; {-9 , 5, 2, 4, 6};EdgeWeightedDiGraph graph &＃61; new EdgeWeightedDiGraph<>(vertexInfo, edges, weight);SPFA spfa &＃61; new SPFA(graph, 0);if (spfa.hasNegativeCycle()) {System.out.print("存在负权环&＃xff1a;");System.out.println(spfa.cycle());}}
}


程序将输出找到的负权回路&＃xff0c;打印[(2->0 2.0), (0->1 -9.0), (1->2 5.0)]。对于不存在负权回路的图&＃xff0c;SPFA当然也能正确处理。这里就不测试了。

代码中特别注意一点&＃xff0c;我们之前有提到需要隔若干次就检查是否存在负权回路&＃xff0c;所以用到一个int型的cost变量记录放松边的次数&＃xff0c;每放松了V条边就检查一次。因为可能在第V次放松之后&＃xff0c;edgeTo[]数组中就存在负权回路了。findNegativeCycle方法就是将edgeTo[]转化成了有向图送给NegativeDiCycle类&＃xff0c;检测是否存在负权回路。

by &＃64;sunhaiyu

2017.9.26