【算法】图

union-find算法

动态连通性

quick-find算法

示意

实现

public void union(int p, int q){
	int pID = find(p);
	int qID = find(q);
	
	if (pID == qID)
		return;
	
	for (int i = 0; i < id.length; i++){
		if (id[i] == pID)
			id[i] = qID;
	}
	
	count--;
}

public int find(int p){
	return id[p];
}

特点

在quick-find算法中，每次find调用只需要访问数组一次，而归并两个分量的union操作访问数组的次数在N+3到2N+1之间。

quick-union算法

示意

实现

public void union(int p, int q){
	int pRoot = find(p);
	int qRoot = find(q);
	
	if (pRoot == qRoot)
		return;
	
	id[pRoot] = qRoot;
	
	count--;
}

public int find(int p){		
	while (id[p] != p)
		p = id[p];
	
	return id[p];
}

特点

quick-union算法中的find方法访问数组的次数为1加上给定触点所对应的节点的深度的两倍。union和connected访问数组的次数为两次find操作（如果union中给定的两个触点分别在不同的树中则还需要加1）。

加权quick-union算法

记录每一棵树的大小并总是将较小的树连接到较大的树上。

示意

实现

public class UnionFind {
	private int[] id;
	private int[] size;
	private int count;
	
	public UnionFind(int n){
		count = n;
		id = new int[n];
		size = new int[n];
		
		for (int i = 0; i < n; i++){
			id[i] = i;
			size[i] = 1;
		}
	}
	
	public int count(){
		return count;
	}
	
	public boolean connected(int p, int q){
		return find(p) == find(q);
	}
	
	public void union(int p, int q){
		int pRoot = find(p);
		int qRoot = find(q);
		
		if (pRoot == qRoot)
			return;
		
		if (size[pRoot] < size[qRoot]){
			id[pRoot] = qRoot;
			size[qRoot] += size[pRoot];
		}
		else{
			id[qRoot] = pRoot;
			size[pRoot] += size[qRoot];
		}
		
		count--;
	}
	
	public int find(int p){		
		while (id[p] != p)
			p = id[p];
		
		return id[p];
	}
}

特点

对于N个触点，加权quick-union算法构造的森林中的任意节点的深度最多为lgN。

对于加权quick-union算法和N个触点，在最坏情况下find、connected和union的成本的增长数量级为lgN。

总结

无向图

深度优先搜索

要搜索一幅图，只需用一个递归方法来遍历所有顶点。在访问其中一个顶点时：

1. 将它标记为已访问
2. 递归地访问它的所有没有被标记过的邻居顶点

如果图是连通的，每个连接链表中的元素都会被检查到。

示意

实现

public class DepthFirstPaths {
	private final int s;
	private boolean[] marked;
	private int[] edgeTo;
	
	public DepthFirstPaths(Graph g, int s){
		this.s = s;
		marked = new boolean[g.V()];
		edgeTo = new int[g.V()];
		dfs(g, s);
	}
	
	private void dfs(Graph g, int v){
		marked[v] = true;
		
		for (int w : g.adj(v)){
			if (marked[w] == false){
				edgeTo[w] = v;
				dfs(g, w);
			}
		}
	}
	
	public boolean hasPathTo(int v){
		return marked[v];
	}
	
	public Iterable<Integer> pathTo(int v){
		if (!hasPathTo(v))
			return null;
		
		Stack<Integer> path = new Stack<Integer>();
		path.push(v);
		
		while (v != s){
			path.push(edgeTo[v]);
			v = edgeTo[v];
		}
		
		return path;
	}
}

特点

深度优先搜索标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比。

使用深度优先搜索得到从给定起点到任意标记顶点的路径所需的时间与路径的长度成正比。

单点路径：给定一幅图和一个起点s，回答“从s到给定目的顶点v是否存在一条路径？如果有，找出这条路径。”等类似问题。

广度优先搜索

使用一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。先将起点加入队列，然后重复以下步骤直到队列为空：

1. 取队列中的下一个顶点v并标记它
2. 将与v相邻的所有未被标记过的顶点加入队列

示意

实现

public class BreadthFirstPaths {
	private final int s;
	private boolean[] marked;
	private int[] edgeTo;
	
	public BreadthFirstPaths(Graph g, int s){
		this.s = s;
		marked = new boolean[g.V()];
		edgeTo = new int[g.V()];
		bfs(g, s);
	}
	
	private void bfs(Graph g, int s){
		Queue<Integer> queue = new Queue<Integer>();
		
		marked[s] = true;
		queue.enqueue(s);
		
		while(!queue.isEmpty()){
			int v = queue.dequeue();
			
			for (int w : g.adj(v)){
				if (marked[w] == false){
					marked[w] = true;
					queue.enqueue(w);
					edgeTo[w] = v;
				}
			}
		}
	}
	
	public boolean hasPathTo(int v){
		return marked[v];
	}
	
	public Iterable<Integer> pathTo(int v){
		if (!hasPathTo(v))
			return null;
		
		Stack<Integer> path = new Stack<Integer>();
		path.push(v);
		
		while (v != s){
			path.push(edgeTo[v]);
			v = edgeTo[v];
		}
		
		return path;
	}
}

特点

对于从s可达的任意顶点v，广度优先搜索都能找到一条从s到v的最短路径（没有其他从s到v的路径所含的边比这条路径更少）。

广度优先搜索所需的时间在最坏情况下和V+E成正比。

单点最短路径：给定一幅图和一个起点s，回答“从s到给定目的顶点v是否存在一条路径？如果有，找出其中最短的那条（所含边数最少）。”等类似问题。

比较

在搜索中都会先将起点存入数据结构中，然后重复以下步骤直到数据结构被清空：

1. 取其中的下一个顶点并标记它
2. 将v的所有相邻而又未被标记的顶点加入数据结构

这两个算法的不同之处仅在于从数据结构中获取下一个顶点的规则（对于广度优先搜索来说是最早加入的顶点，对于深度优先搜索来说是最晚加入的顶点）。

连通分量

深度优先搜索的直接应用是找出一幅图的所有连通分量。它能够将所有顶点切分为等价类。

示意

实现

public class ConnectedComponents {
	private int count;
	private boolean[] marked;
	private int[] id;
	
	public ConnectedComponents(Graph g){
		count = 0;
		marked = new boolean[g.V()];
		id = new int[g.V()];
		
		for (int s = 0; s < g.V(); s++){
			if (marked[s] == false){
				dfs(g, s);
				count++;
			}
		}
	}
	
	private void dfs(Graph g, int v){
		marked[v] = true;
		id[v] = count;
		
		for (int w : g.adj(v)){
			if (marked[w] == false)
				dfs(g, w);
		}
	}
	
	public boolean connected(int v, int w){
		return id[v] == id[w];
	}
	
	public int id(int v){
		return id[v];
	}
	
	public int count(){
		return count;
	}
}

特点

深度优先搜索的预处理使用的时间和空间与V+E成正比且可以在常数时间内处理关于图的连通性查询。

比较

union-find算法其实更快，因为它不需要完整地构造并表示一幅图，是一种动态算法（在任何时候都能用接近常数的时间检查两个顶点是否连通，甚至是在添加一条边的时候），但深度优先搜索则必须要对图进行预处理。因此，在完成只需要判断连通性或是需要完成有大量连通性查询和插入操作混合等类似的任务时，更倾向使用union-find算法，而深度优先搜索则更适合实现图的抽象数据类型，因为它能更有效地利用已有的数据结构。

检测环

给定的图是无环图吗？

实现

public class Cycle {
	private boolean[] marked;
	private boolean hasCycle;
	
	public Cycle(Graph g){
		marked = new boolean[g.V()];
		hasCycle = false;
		
		for (int s = 0; s < g.V(); s++){
			if (marked[s] == false)
				dfs(g, s, s);
		}
	}
	
	private void dfs(Graph g, int v, int p){
		marked[v] = true;
		
		for (int w : g.adj(v)){
			if (marked[w] == false)
				dfs(g, w, v);
			else if (w != p)
				hasCycle = true;
		}
	}
	
	public boolean hasCycle(){
		return hasCycle;
	}
}

双色问题

能够用两种颜色将图的所有顶点着色，使得任意一条边的两个端点的颜色都不相同吗？（这是一幅二分图吗？）

实现

public class TwoColor {
	private boolean[] marked;
	private boolean[] color;
	private boolean isTwoColorable;
	
	public TwoColor(Graph g){
		marked = new boolean[g.V()];
		color = new boolean[g.V()];
		isTwoColorable = true;
		
		for (int s = 0; s < g.V(); s++){
			if (marked[s] == false)
				dfs(g, s);
		}
	}
	
	private void dfs(Graph g, int v){
		marked[v] = true;
		
		for (int w : g.adj(v)){
			if (marked[w] == false){
				color[w] = !color[v];
				dfs(g, w);
			}
			else if (color[w] == color[v])
				isTwoColorable = false;
		}
	}
	
	public boolean isBipartite(){
		return isTwoColorable;
	}
}

有向图

深度优先搜索

实现

public class DepthFirstDirectedPaths {
	private final int s;
	private boolean[] marked;
	private int[] edgeTo;
	
	public DepthFirstDirectedPaths(Digraph g, int s){
		this.s = s;
		marked = new boolean[g.V()];
		edgeTo = new int[g.V()];
		dfs(g, s);
	}
	
	private void dfs(Digraph g, int v){
		marked[v] = true;
		
		for (int w : g.adj(v)){
			if (marked[w] == false){
				edgeTo[w] = v;
				dfs(g, w);
			}
		}
	}
	
	public boolean hasPathTo(int v){
		return marked[v];
	}
	
	public Iterable<Integer> pathTo(int v){
		if (!hasPathTo(v))
			return null;
		
		Stack<Integer> path = new Stack<Integer>();
		path.push(v);
		
		while (v != s){
			path.push(edgeTo[v]);
			v = edgeTo[v];
		}
		
		return path;
	}
}

特点

在有向图中，深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比。

单向有向路径给定一幅有向图和一个起点s，回答“从s到给定目的顶点v是否存在一条有向路径？如果有，找出这条路径。”等类似问题。

广度优先搜索

实现

public class BreadthFirstDirectedPaths {
	private final int s;
	private boolean[] marked;
	private int[] edgeTo;
	
	public BreadthFirstDirectedPaths(Digraph g, int s){
		this.s = s;
		marked = new boolean[g.V()];
		edgeTo = new int[g.V()];
		bfs(g, s);
	}
	
	private void bfs(Digraph g, int v){
		Queue<Integer> queue = new Queue<Integer>();
		
		marked[v] = true;
		queue.enqueue(v);
		
		while (!queue.isEmpty()){
			int x = queue.dequeue();
			
			for (int w : g.adj(x)){
				if (marked[w] == false){
					marked[w] = true;
					edgeTo[w] = x;
					queue.enqueue(w);
				}
			}
		}
	}
	
	public boolean hasPathTo(int v){
		return marked[v];
	}
	
	public Iterable<Integer> pathTo(int v){
		if (!hasPathTo(v))
			return null;
		
		Stack<Integer> path = new Stack<Integer>();
		path.push(v);
		
		while (v != s){
			path.push(edgeTo[v]);
			v = edgeTo[v];
		}
		
		return path;
	}
}

特点

单点最短有向路径给定一幅有向图和一个起点s，回答“从s到给定目的顶点v是否存在一条有向路径？如果有，找出其中最短的那条（所含边数最少）。”等类似问题。

有向环检测

给定的有向图中包含有向环吗？如果有，按照路径的方向从某个顶点并返回自己来找到环上的所有顶点。

定义

有向无环图（DAG）就是一幅不含有环的有向图。

示意

实现

public class DirectedCycle {
	private boolean[] marked;
	private int[] edgeTo;
	private boolean[] onStack;
	private Stack<Integer> cycle;
	
	public DirectedCycle(Digraph g){
		marked = new boolean[g.V()];
		edgeTo = new int[g.V()];
		onStack = new boolean[g.V()];
		
		for (int v = 0; v < g.V(); v++){
			if (marked[v] == false)
				dfs(g, v);
		}
	}
	
	private void dfs(Digraph g, int v){
		marked[v] = true;
		onStack[v] = true;
		
		for (int w : g.adj(v)){
			if (hasCycle())
				return;
			else if (marked[w] == false){
				edgeTo[w] = v;
				dfs(g, w);
			}
			else if (onStack[w] == true){
				cycle = new Stack<Integer>();
				int x = v;
				
				cycle.push(x);
				
				while (x != w){
					cycle.push(edgeTo[x]);
					x = edgeTo[x];
				}
				
				cycle.push(v);
			}
		}
		
		onStack[v] = false;
	}
	
	public boolean hasCycle(){
		return cycle != null;
	}
	
	public Iterable<Integer> cycle(){
		return cycle;
	}
}

拓扑排序

给定一幅有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素（或者说明无法做到这一点）。

定义

当且仅当一幅有向图是无环图时它才能进行拓扑排序。

一幅有向无环图的拓扑排序即为所有顶点的逆后序排列。

基于深度优先搜索的顶点排序

将dfs的参数顶点保存在一个数据结构中，遍历这个数据结构实际上就能访问图中的所有顶点。顶点有以下三种排列顺序：

1. 前序：在递归调用之前将顶点加入队列
2. 后序：在递归调用之后将顶点加入队列
3. 逆后序：在递归调用之后将顶点压入栈

示意

实现

public class DepthFirstOrder {
	private boolean[] marked;
	private Queue<Integer> pre;
	private Queue<Integer> post;
	private Stack<Integer> reversePost;
	
	public DepthFirstOrder(Digraph g){
		marked = new boolean[g.V()];
		pre = new Queue<Integer>();
		post = new Queue<Integer>();
		reversePost = new Stack<Integer>();
		
		for (int v = 0; v < g.V(); v++){
			if (marked[v] == false)
				dfs(g, v);
		}
	}
	
	private void dfs(Digraph g, int v){
		marked[v] = true;
		pre.enqueue(v);
		
		for (int w : g.adj(v)){
			if (marked[w] == false)
				dfs(g, w);
		}
		
		post.enqueue(v);
		reversePost.push(v);
	}
	
	public Iterable<Integer> pre(){
		return pre;
	}
	
	public Iterable<Integer> post(){
		return post;
	}
	
	public Iterable<Integer> reversePost(){
		return reversePost;
	}
}

示意

实现

public class Topological {
	private Iterable<Integer> order;
	
	public Topological(Digraph g){
		DirectedCycle cycle = new DirectedCycle(g);
		
		if (!cycle.hasCycle()){
			DepthFirstOrder dfs = new DepthFirstOrder(g);
			
			order = dfs.reversePost();
		}
	}
	
	public Iterable<Integer> order(){
		return order;
	}
	
	public boolean isDAG(){
		return order != null;
	}
}

特点

使用深度优先搜索对有向无环图进行拓扑排序所需的时间和V+E成正比。

强连通性

使用深度优先搜索查找给定有向图G的反向图G’，根据由此得到的所有顶点的逆后序再次用深度优先搜索处理有向图G（Kosaraju算法），其构造函数中的每一次递归调用所标记的顶点都在同一个强连通分量之中。

示意

实现

public class KosarajuSCC {
	private boolean[] marked;
	private int[] id;
	private int count;
	
	public KosarajuSCC(Digraph g){
		marked = new boolean[g.V()];
		id = new int[g.V()];
		count = 0;
		
		DepthFirstOrder order = new DepthFirstOrder(g.reverse());
		for (int v : order.reversePost()){
			if (marked[v] == false){
				dfs(g, v);
				count++;
			}
		}
	}
	
	private void dfs(Digraph g, int v){
		marked[v] = true;
		id[v] = count;
		
		for (int w : g.adj(v)){
			if (marked[w] == false)
				dfs(g, w);
		}
	}
	
	public boolean stronglyConnected(int v, int w){
		return id[v] == id[w];
	}
	
	public int id(int v){
		return id[v];
	}
	
	public int count(){
		return count;
	}
}

特点

Kosaraju算法的预处理所需的时间和空间与V+E成正比且支持常数时间的有向图强连通性的查询。

给定一幅有向图，回答“给定的两个顶点是强连通的吗？这幅有向图中含有多少个强连通分量？”等类似问题。

最小生成树

Prim算法

每一步都会为一棵生长中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边（黑色表示）加入树中（即由树中的顶点所定义的切分中的一条横向边）。

每当向树中添加了一条边之后，也向树中添加了一个顶点。要维护一个包含所有横切边的集合，就要将连接这个顶点和其他所有不在树中的顶点的边加入优先队列。但，连接新加入树中的顶点与其他已经在树中顶点的所有边都失效了。（这样的边都已经不是横切边了，因为它的两个顶点都在树中。）

示意

定义

Prim算法能够得到任意加权无向图的最小生成树。

延时实现

将失效的边先留在优先队列中，等到要删除它们的时候再检查边的有效性。

示意

实现

public class LazyPrimMST {
	private double weight;
	private boolean[] marked;
	private Queue<Edge> mst;
	private MinPQ<Edge> pq;
	
	public LazyPrimMST(EdgeWeightedGraph g){
		weight = 0;
		marked = new boolean[g.V()];
		mst = new Queue<Edge>();
		pq = new MinPQ<Edge>(g.E());
		
		prim(g);
	}
	
	private void prim(EdgeWeightedGraph g){
		visit(g, 0);
		
		while (!pq.isEmpty()){
			Edge e = pq.delMin();
			
			int v = e.either();
			int w = e.other(v);
			
			if (marked[v] == true && marked[w] == true)
				continue;
			
			weight += e.weight();
			mst.enqueue(e);
			
			if (marked[v] == false)
				visit(g, v);
			else if (marked[w] == false)
				visit(g, w);
		}
	}
	
	private void visit(EdgeWeightedGraph g, int v){
		marked[v] = true;
		
		for (Edge e : g.adj(v)){
			if (marked[e.other(v)] == false)
				pq.insert(e);
		}
	}
	
	public Iterable<Edge> edges(){
		return mst;
	}
	
	public double weight(){
		return weight;
	}
}

特点

Prim算法的延时实现计算一幅含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间与E成正比，所需的时间与ElogE成正比（最坏情况）。

即时实现

只会在优先队列中保存每个非树顶点w的一条边：将它与树中的顶点连接起来的权重最小的那条边。将w和树的顶点连接起来的其他权重较大的边迟早都会失效，所以没必要在优先队列中保存它们。

示意

实现

public class PrimMST {
	private boolean[] marked;
	private Edge[] edgeTo;
	private double[] distTo;
	private IndexMinPQ<Double> pq;
	
	public PrimMST(EdgeWeightedGraph g){
		marked = new boolean[g.V()];
		edgeTo = new Edge[g.V()];
		distTo = new double[g.V()];
		pq = new IndexMinPQ<Double>(g.V());
		
		for (int v = 0; v < g.V(); v++)
			distTo[v] = Double.POSITIVE_INFINITY;
		
		prim(g);
	}
	
	private void prim(EdgeWeightedGraph g){
		pq.insert(0, 0.0);
		
		while (!pq.isEmpty())
			visit(g, pq.delMin());
	}
	
	private void visit(EdgeWeightedGraph g, int v){
		marked[v] = true;
		
		for (Edge e : g.adj(v)){
			int w = e.other(v);
			
			if (marked[w] == true)
				continue;
			
			if (e.weight() < distTo[w]){
				distTo[w] = e.weight();
				edgeTo[w] = e;
				
				if (pq.contains(w))
					pq.change(w, distTo[w]);
				else
					pq.insert(w, distTo[w]);
			}
		}
	}
	
	public Iterable<Edge> edges(){
		Queue<Edge> mst = new Queue<Edge>();
		
		for (int v = 1; v < edgeTo.length; v++)
			mst.enqueue(edgeTo[v]);
		
		return mst;
	}
	
	public double weight(){
		double weight = 0.0;
		
		for (int v = 1; v < distTo.length; v++)
			weight += distTo[v];
		
		return weight;
	}
}

特点

Prim算法的即时实现计算一幅含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间和V成正比，所需的时间和ElogV成正比（最坏情况）。

Kruskal算法

按照边的权重顺序（从小到大）处理它们，将边加入最小生成树中，加入的边不会与已经加入的边构成环，直到树中含有V-1条边为止。这些黑色的边逐渐由一片森林合并为一棵树，也就是图的最小生成树。

定义

Kruskal算法能够计算任意加权无向图的最小生成树。

示意

实现

public class KruskalMST {
	private Queue<Edge> mst;
	private MinPQ<Edge> pq;
	private UnionFind uf;
	private double weight;
	
	public KruskalMST(EdgeWeightedGraph g){
		weight = 0;
		mst = new Queue<Edge>();
		pq = new MinPQ<Edge>(g.E());
		uf = new UnionFind(g.V());
		
		for (Edge e : g.edges())
			pq.insert(e);
		
		kruskal(g);
	}
	
	private void kruskal(EdgeWeightedGraph g){
		while (!pq.isEmpty() && mst.size() < g.V()){
			Edge e = pq.delMin();
			
			int v = e.either();
			int w = e.other(v);
			
			if (uf.connected(v, w))
				continue;
			
			uf.union(v, w);
			mst.enqueue(e);
			weight += e.weight();
		}
	}
	
	public Iterable<Edge> edges(){
		return mst;
	}
	
	public double weight(){
		return weight;
	}
}

特点

Kruskal算法计算一幅含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间和E成正比，所需的时间和ElogE成正比（最坏情况）。

比较

Prim算法是一条边一条边地来构造最小生成树，每一步都为一棵树添加一条边。 Kruskal算法构造最小生成树的时候也是一条边一条边地构造，但不同的是它寻找的边会连接一片森林中的两棵树。从一片由V棵单顶点的树构成的森林开始并不断将两棵树合并（用可以找到的最短边）直到只剩下一棵树，它就是最小生成树。

总结

最短路径树

Dijkstra算法

采用了类似Prim算法的方法来计算最短路径树。

定义

Dijkstra算法能够解决边权重非负的加权有向图的单起点最短路径问题。

示意

实现

public class DijkstraSPT {
	private DirectedEdge[] edgeTo;
	private double[] distTo;
	private IndexMinPQ<Double> pq;
	private int s;
	
	public DijkstraSPT(EdgeWeightedDigraph g, int s){
		edgeTo = new DirectedEdge[g.V()];
		distTo = new double[g.V()];
		pq = new IndexMinPQ<Double>(g.V());
		this.s = s;
		
		for (int v = 0; v < g.V(); v++)
			distTo[v] = Double.POSITIVE_INFINITY;
		distTo[s] = 0;
		
		pq.insert(s, 0.0);
		
		while (!pq.isEmpty())
			relax(g, pq.delMin());
	}
	
	private void relax(EdgeWeightedDigraph g, int v){
		for (DirectedEdge e : g.adj(v)){
			int w = e.to();
			
			if (distTo[v] + e.weight() < distTo[w]){
				distTo[w] = distTo[v] + e.weight();
				edgeTo[w] = e;
				
				if (pq.contains(w))
					pq.change(w, distTo[w]);
				else
					pq.insert(w, distTo[w]);
			}
		}
	}
	
	public double distTo(int v){
		return distTo[v];
	}
	
	public boolean hasPathTo(int v){
		return distTo[v] < Double.POSITIVE_INFINITY;
	}
	
	public Iterable<DirectedEdge> pathTo(int v){
		if (!hasPathTo(v))
			return null;
		
		Stack<DirectedEdge> path = new Stack<DirectedEdge>();
		
		DirectedEdge e = edgeTo[v];
		
		while (e.from() != s){
			path.push(e);
			e = edgeTo[e.from()];
		}
		
		path.push(e);
		
		return path;
	}
}

特点

在一幅含有V个顶点和E条边的加权有向图中，使用Dijkstra算法计算根结点为给定起点的最短路径树所需的空间与V成正比，时间与ElogV成正比（最坏情况下）。

比较

Prim算法每次添加的都是离树最近的非树顶点，Dijkstra算法每次添加的都是离起点最近的非树顶点。

拓扑排序

将顶点的放松和拓扑排序结合起来。

示意

实现

public class AcyclicSPT {
	private DirectedEdge[] edgeTo;
	private double[] distTo;
	private int s;
	
	public AcyclicSPT(EdgeWeightedDigraph g, int s){
		edgeTo = new DirectedEdge[g.V()];
		distTo = new double[g.V()];
		this.s = s;
		
		for (int v = 0; v < g.V(); v++)
			distTo[v] = Double.POSITIVE_INFINITY;
		distTo[s] = 0;
		
		Topological t = new Topological(g);
		
		for (int v : t.order())
			relax(g, v);
	}
	
	private void relax(EdgeWeightedDigraph g, int v){
		for (DirectedEdge e : g.adj(v)){
			int w = e.to();
			
			if (distTo[v] + e.weight() < distTo[w]){
				distTo[w] = distTo[v] + e.weight();
				edgeTo[w] = e;
			}
		}
	}
	
	public double distTo(int v){
		return distTo[v];
	}
	
	public boolean hasPathTo(int v){
		return distTo[v] < Double.POSITIVE_INFINITY;
	}
	
	public Iterable<DirectedEdge> pathTo(int v){
		if (!hasPathTo(v))
			return null;
		
		Stack<DirectedEdge> path = new Stack<DirectedEdge>();
		
		DirectedEdge e = edgeTo[v];
		
		while (e.from() != s){
			path.push(e);
			e = edgeTo[e.from()];
		}
		
		path.push(e);
		
		return path;
	}
}

特点

按照拓扑排序放松顶点，就能在和E+V成正比的时间内解决无环有向图的单点最短路径问题。

1. 能够在线性时间内解决单点最短路径问题
2. 能够处理负权重的边
3. 能够解决相关的问题，例如找出最长的路径

Bellman-Ford算法

解决一般有向图中的以下问题：

1. 负权重环的检测。给定的加权有向图中含有负权重环吗？如果有，找到它。
2. 负权重环不可达时的单点最短路径。给定一幅加权有向图和一个起点s且从s无法到达任何负权重环，回答“是否存在一条从s到给定的顶点v的有向路径？如果有，找出最短（总权重最小）的那条路径。“等类似问题。

定义

在任意含有V个顶点的加权有向图中给定起点s，从s无法到达任何负权重环，以下算法能够解决其中的单点最短路径问题：以任意顺序放松有向图的所有边，重复V轮。

示意

负权重环的检测

在将所有边放松V轮之后当且仅当队列非空时有向图中才存在从起点可达的负权重环。

示意

实现

public class BellmanFordSPT {
	private DirectedEdge[] edgeTo;
	private double[] distTo;
	private Iterable<DirectedEdge> cycle;
	private Queue<Integer> queue;
	private boolean[] onQ;
	private int s;
	private int cost;
	
	public BellmanFordSPT(EdgeWeightedDigraph g, int s){
		this.s = s;
		cost = 0;
		edgeTo = new DirectedEdge[g.V()];
		distTo = new double[g.V()];
		onQ = new boolean[g.V()];
		queue = new Queue<Integer>();
		
		for (int v = 0; v < g.V(); v++)
			distTo[v] = Double.POSITIVE_INFINITY;
		distTo[s] = 0;
		
		onQ[s] = true;
		queue.enqueue(s);
		
		while (!queue.isEmpty() && !hasNegativeCycle()){
			int v = queue.dequeue();
			onQ[v] = false;
			relax(g, v);
			
			if (++cost % g.V() == 0)
				findNegativeCycle();
		}
	}
	
	private void relax(EdgeWeightedDigraph g, int v){
		for (DirectedEdge e : g.adj(v)){
			int w = e.to();
			
			if (distTo[v] + e.weight() < distTo[w]){
				distTo[w] = distTo[v] + e.weight();
				edgeTo[w] = e;
				
				if (onQ[w] == false){
					onQ[w] = true;
					queue.enqueue(w);
				}
			}
		}
	}
	
	private void findNegativeCycle(){
		int V = edgeTo.length;
		
		EdgeWeightedDigraph g = new EdgeWeightedDigraph(V);
		
		for (int v = 0; v < V; v++){
			if (edgeTo[v] != null)
				g.addEdge(edgeTo[v]);
		}
		
		EdgeWeightedDirectedCycle c = new EdgeWeightedDirectedCycle(g);
		
		cycle = c.cycle();
	}
	
	public boolean hasNegativeCycle(){
		return cycle != null;
	}
	
	public Iterable<DirectedEdge> negativeCycle(){
		return cycle;
	}
	
	public double distTo(int v){
		return distTo[v];
	}
	
	public boolean hasPathTo(int v){
		return distTo[v] < Double.POSITIVE_INFINITY;
	}
	
	public Iterable<DirectedEdge> pathTo(int v){
		if (!hasPathTo(v))
			return null;
		
		Stack<DirectedEdge> path = new Stack<DirectedEdge>();
		
		DirectedEdge e = edgeTo[v];
		
		while (e.from() != s){
			path.push(e);
			e = edgeTo[e.from()];
		}
		
		path.push(e);
		
		return path;
	}
}

特点

对于任意含有V个顶点的加权有向图和给定的起点s，在最坏情况下基于队列的Bellman-Ford算法解决最短路径问题（或者找到从s可达的负权重环）所需的时间和EV成正比，空间和V成正比。

总结