▶ 书中第四章部分程序，包括在加上自己补充的代码，在有权有向图中寻找环，Bellman - Ford 算法求最短路径，套汇算法
● 在有权有向图中寻找环
package package01; import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.DirectedEdge;
import edu.princeton.cs.algs4.EdgeWeightedDigraph;
import edu.princeton.cs.algs4.Stack; public class class01
{
private boolean[] marked;
private DirectedEdge[] edgeTo;
private boolean[] onStack; // 各顶点当前是否在搜索栈中，递归回退时要清空
private Stack<DirectedEdge> cycle; // 存储环，若空则表示图中不存在环 public class01(EdgeWeightedDigraph G)
{
marked = new boolean[G.V()];
edgeTo = new DirectedEdge[G.V()];
onStack = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
{
if (!marked[v])
dfs(G, v);
}
} private void dfs(EdgeWeightedDigraph G, int v)
{
marked[v] = true;
onStack[v] = true;
for (DirectedEdge e : G.adj(v))
{
int w = e.to();
if (cycle != null) // 已经有环了
return;
if (!marked[w])
{
edgeTo[w] = e;
dfs(G, w);
}
else if (onStack[w]) // 该点已经遍历过，且在栈中，即有环
{
cycle = new Stack<DirectedEdge>();
DirectedEdge f = e;
for (; f.from() != w; f = edgeTo[f.from()]) // 回退搜索栈压入 cycle 中，直到该环在搜索栈中的首元素 w 处
cycle.push(f);
cycle.push(f); // 压入环在搜索栈中的首元素 w
return;
}
}
onStack[v] = false; // 递归回退时栈要清空，但 marked 不清空
} public boolean hasCycle()
{
return cycle != null;
} public Iterable<DirectedEdge> cycle()
{
return cycle;
} public static void main(String[] args)
{
int V = Integer.parseInt(args[0]); // 新建有边权有向图 G(E,V)，再添加 F 条边
int E = Integer.parseInt(args[1]);
int F = Integer.parseInt(args[2]);
EdgeWeightedDigraph G = new EdgeWeightedDigraph(V);
int[] vertices = new int[V];
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
for (int i = 0; i < E; i++)
{
int v = 1, w = 0;
for (; v >= w; v = StdRandom.uniform(V), w = StdRandom.uniform(V));
double weight = StdRandom.uniform();
G.addEdge(new DirectedEdge(v, w, weight));
}
for (int i = 0; i < F; i++)
{
int v = StdRandom.uniform(V), w = StdRandom.uniform(V);
double weight = StdRandom.uniform(0.0, 1.0);
G.addEdge(new DirectedEdge(v, w, weight));
} StdOut.println(G); // 原图
class01 finder = new class01(G); // 搜索环
if (finder.hasCycle())
{
StdOut.print("Cycle: ");
for (DirectedEdge e : finder.cycle())
StdOut.print(e + " ");
StdOut.println();
}
else
StdOut.println("No directed cycle");
}
}
● Bellman - Ford 算法求最短路径
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.DirectedEdge;
import edu.princeton.cs.algs4.EdgeWeightedDigraph;
import edu.princeton.cs.algs4.EdgeWeightedDirectedCycle;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.Queue; public class class01
{
private double[] distTo; // 起点到各顶点的距离
private DirectedEdge[] edgeTo; // 起点到各顶点的最后一条边
private boolean[] onQueue; // 各顶点当前是否在搜索队中
private Queue<Integer> queue; // 搜索队列
private int cost; // 调用函数 relax 的次数
private Iterable<DirectedEdge> cycle; // 存储负环，若空则表示图中不存在负环 public class01(EdgeWeightedDigraph G, int s)
{
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
onQueue = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
queue = new Queue<Integer>();
for (queue.enqueue(s), onQueue[s] = true; !queue.isEmpty() && !hasNegativeCycle();) // 存在负环则停止搜索
{
int v = queue.dequeue(); // 每次从搜索队列中拿走一个顶点，松弛以该顶点为起点的边
onQueue[v] = false;
relax(G, v);
}
} private void relax(EdgeWeightedDigraph G, int v)
{
for (DirectedEdge e : G.adj(v))
{
int w = e.to();
if (distTo[w] > distTo[v] + e.weight()) // 加入这条边会使起点到 w 的距离变短
{
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (!onQueue[w]) // 注意若 w 已经在搜索队列中则不做任何改变
{
queue.enqueue(w);
onQueue[w] = true;
}
}
if (cost++ % G.V() == 0) // 每当松弛了 V 的倍数次时检查是否存在负环
{
findNegativeCycle();
if (hasNegativeCycle())
return;
}
}
} private void findNegativeCycle() // 利用类 EdgeWeightedDirectedCycle 来找环
{
int V = edgeTo.length;
EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
for (int v = 0; v < V; v++)
{
if (edgeTo[v] != null)
spt.addEdge(edgeTo[v]);
}
EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
cycle = finder.cycle();
} public boolean hasNegativeCycle()
{
return cycle != null;
} public Iterable<DirectedEdge> negativeCycle()
{
return cycle;
} public boolean hasPathTo(int v)
{
return distTo[v] < Double.POSITIVE_INFINITY;
} public double distTo(int v)
{
if (hasNegativeCycle())
throw new UnsupportedOperationException("\n<distTo> Negative cost cycle exists.\n");
return distTo[v];
} public Iterable<DirectedEdge> pathTo(int v)
{
if (hasNegativeCycle())
throw new UnsupportedOperationException("\n<pathTo> Negative cost cycle exists.\n");
if (!hasPathTo(v))
return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
path.push(e);
return path;
} public static void main(String[] args)
{
In in = new In(args[0]);
int s = Integer.parseInt(args[1]);
EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
class01 sp = new class01(G, s);
if (sp.hasNegativeCycle())
{
for (DirectedEdge e : sp.negativeCycle())
StdOut.println(e);
}
else
{
for (int v = 0; v < G.V(); v++)
{
if (sp.hasPathTo(v))
{
StdOut.printf("%d to %d (%5.2f) ", s, v, sp.distTo(v));
for (DirectedEdge e : sp.pathTo(v))
StdOut.print(e + " ");
StdOut.println();
}
else
StdOut.printf("%d to %d no path\n", s, v);
}
}
}
}
● 套汇，本质是寻找负环
package package01; import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.DirectedEdge;
import edu.princeton.cs.algs4.EdgeWeightedDigraph;
import edu.princeton.cs.algs4.BellmanFordSP; public class class01
{
private class01() {} public static void main(String[] args)
{
int V = StdIn.readInt(); // 顶点数
String[] name = new String[V];
EdgeWeightedDigraph G = new EdgeWeightedDigraph(V);
for (int v = 0; v < V; v++) // 建图
{
name[v] = StdIn.readString();
for (int w = 0; w < V; w++)
{
double rate = StdIn.readDouble();
DirectedEdge e = new DirectedEdge(v, w, -Math.log(rate));// 汇率取负对数，x1x2x3 < 1 -> -logx1 -logx2 -logx3 < 0
G.addEdge(e);
}
}
BellmanFordSP spt = new BellmanFordSP(G, 0); // 用 BF 算法找负环
if (spt.hasNegativeCycle())
{
double stake = 1000.0;
for (DirectedEdge e : spt.negativeCycle())
{
StdOut.printf("%10.5f %s ", stake, name[e.from()]);
stake *= Math.exp(-e.weight());
StdOut.printf("= %10.5f %s\n", stake, name[e.to()]);
}
}
else
StdOut.println("No arbitrage opportunity");
}
}