加权有向图问题1--单源最短路径问题（Dijkstra算法和Bellman - Ford算法）

加权有向图实现

我们实现两个类，权重边类和有向图类。有向图类中组合权重边类来实现加权有向图。

权重边类实现：

public class DirectedEdge {private int v;private int w;private double weight;public DirectedEdge(int v,int w,double weight) {this.v = v;this.w = w;this.weight = weight;}public double weight(){  return weight;  }public int form(){  return v;  }public int to(){  return w;  }public String toString(){  return String.format("%d->%d %.2f", v,w,weight);  }
}

加权有向图实现：

public class EdgeWeightedDigraph {private int V;//顶点数private int E;//边数private Bag<DirectedEdge>[] adj;//邻接表public EdgeWeightedDigraph(int V) {this.V = V;this.E = 0;adj = (Bag<DirectedEdge>[]) new Bag[V];for(int v=0;v< V;v++) {adj[v] = new Bag<DirectedEdge>();}}public int V() {return V;}public int E() {return E;}public void addEdge(DirectedEdge e) {adj[e.form()].add(e);E++;}//从v指出的边public Iterable<DirectedEdge> adj(int v){return adj[v];}//该有向图中所有的边public Iterable<DirectedEdge> edges(){Bag<DirectedEdge> bag = new Bag<DirectedEdge>();for(int v = 0; v<V; v++)for(DirectedEdge e : adj[v])bag.add(e);return bag;}
}

Dijkstra算法

Dijkstra算法可以解决边的权重非负的最短路径问题，无法判断含负权边的图的最短路径，但Bellman-Ford算法可以。

边的松弛：

在实现Dijkstra算法之前，必须先了解边的松弛：松弛边v->w意味着检查从s到w的最短路径是否是先从s到v，再从v到w。如果是，则根据这个情况更新数据。下面的代码实现了放松一个从给定顶点的指出的所有的边：

private void relax(EdgeWeightedDigraph G,int v) {for(DirectedEdge e: G.adj(v)) {int w = e.to();if(distTo[w]>distTo[v]+e.weight()) {distTo[w] = distTo[v]+e.weight();edgeTo[w] = e;}}
}

其中，distTo[]是一个顶点索引数组，保存的是G中路径的长度。对于从s可达的所有顶点w，distTo[v]的值是从s到w的某条路径长度，对于s不可达的所有顶点w，该值为无穷大。

数据结构：

• 最短路径树中的边：使用一个由顶点索引的父链接数组edgeTo[],其中edgeTo[v]的值为树中连接v和它父节点的边（也是从s到v的最短路径上的最后一条边），通过该数组可以逆推得到最短路径。
• 到达起点的距离：用一个由顶点索引的数组distTo[]，其中distTo[v]为从s到v的已知最短路径的长度。
• 顶点优先权队列：保存需要被放松的顶点并确认下一个被放松的顶点。

算法实现：

public class DijkstraSP {private DirectedEdge[] edgeTo;  //edgeTo用来逆推最短路径private double[] distTo;    //distTo[]用来计算最短路径private IndexMinPQ<Double> pq;    //用来保存需要被放松的顶点并确认下一个被放松的顶点public DijkstraSP(EdgeWeightedDigraph G,int s) {//初始化edgeTo = new DirectedEdge[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;distTo[s] = 0.0;//从起始顶点s开始pq.insert(s,0.0);    //调用优先权队列的insert()方法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[w]>distTo[v]+e.weight()) {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>();for(DirectedEdge e = edgeTo[v];e!=null;e = edgeTo[e.form()])path.push(e);return path;}
}

简单的在上述算法外添加一层循环即可实现任意顶点对之间的最短路径（权重非负）。

无环情况下的最短路径算法

算法特点：

如果加权有向图不含有向环，则下面要实现的算法比Dijkstra算法更快更简单。它有以下特点：

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

算法思想：

该方法将顶点的放松与拓扑排序结合起来，首先将distTo[s]初始化为0，其他distTo[]初始化为无穷大，然后一个个地按照拓扑排序放松所有顶点。

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

算法实现：

public class AcyclicSP {private DirectedEdge[] edgeTo;private double[] distTo;public AcyclicSP(EdgeWeightedDigraph G,int s) {//初始化edgeTo = new DirectedEdge[G.V()];distTo = new double[G.V()];for(int v = 0;v<G.V();v++)distTo[v] = Double.POSITIVE_INFINITY;distTo[s] = 0.0;//拓扑排序对象Tolpological top = new Tolpological(G);//按照拓扑排序放松顶点for(int v: top.order())    relax(G,v);}//relax()、distTo()、hasPathTo()、pathTo()同Dijkstra算法
}

改实现中不需要marked[]数组，因为按照拓扑排序处理不可能再次遇到已经被放松过的顶点。

Bellman-Ford算法

Dijkstra算法无法判断含负权边的图的最短路径，如果遇到负权，在没有负权回路（回路的权值和为负）存在时，可以采用Bellman - Ford算法正确求出最短路径。

当且仅当加权有向图中至少存在一条从s到v的有向路径且所有从s到v的有向路径上的任意顶点都不存在与任何负权重环中，s到v的最短路径才是存在的。

算法思想：

在任意含有V个顶点的加权有向图中给定起点s，从s无法达到任何负权重环，一下算法能够解决其中的单源最短路径问题：将distTo[s]初始化为0，其他distTo[]初始化为无穷大。以任意顺序放松所有边，重复V轮。

算法实现：

这个算法非常简洁通用，在进行过负权重检测（见最后）之后，下面代码就可以实现Bellman-Ford算法：

for(int num = 0; num<G.V(); num++)for(v = 0;v<G.V();v++)for(DirectedEdge e: G.adj(v))relax(e);

但根据经验可知在任意一轮中许多边的放松是不会成功的：只有上一轮distTo[]值发生变化的顶点指出的边才能够改变其他distTo[]的值。为了记录这样的顶点，引入一条FIFO队列。

算法改进：

Bellman-Ford算法所需时间和EV成正比，空间和V成正比。

数据结构：

• 一条用来保存即将被放松的顶点的队列
• 一个由顶点索引的boolean[]数组，用来指示顶点是否已经在队列中

算法思想：

首先，将起始顶点s加入队列中，然后进入一个循环，其中每次都从队列中取出一个顶点将其放松。然后将被成功放松的边所指向的顶点加入队列中，这样能保证：

• 队列中不会出现重复的顶点
• 在某一轮中，改变了distTo[]和edgeTo[]的值的所有顶点都会在下一轮中处理

算法实现：

放松边：

private void relax(EdgeWeightedDigraph G,int v) {for(DirectedEdge e: G.adj(v)) {int w = e.to();if(distTo[w]>distTo[v]+e.weight()) {distTo[w] = distTo[v]+e.weight();edgeTo[w] = e;if(!onQ[w]) {queue.enqueue(w);onQ[w] = true;}}if(cost++%G.V()==0)findNegativeCycle();}
}

算法实现：

public class BellmanFordSP {private double [] distTo;	//从起点到某个顶点的路径长度private DirectedEdge[] edgeTo;		//从起点到某个顶点的最后一条边private boolean[] onQ;		//该顶点是否存在于队列中private Queue<Integer> queue;		//正在被放松的顶点private int cost;		//relax()的调用次数private Iterable<DirectedEdge> cycle;		//edgeTo[]中是否含有负权重环public BellmanFordSP(EdgeWeightedDigraph G,int s) {distTo = new double[G.V()];edgeTo = new DirectedEdge[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[0] = 0.0;queue.enqueue(s);onQ[s] = true;while(!queue.isEmpty()&&!hasNegativeCycle()) {int v = queue.dequeue();onQ[v] = false;relax(G,v);}}private void relax(EdgeWeightedDigraph G,int v) {}//见上文算法public boolean hasPathTo(int v) {}//与Dijkstra算法中方法相同public Iterable<DirectedEdge> pathTo(int v){}//与Dijkstra算法中方法相同/********************************************************************************************///负权重检测private void findNegativeCycle() {int V = edgeTo.length;EdgeWeightedDigraph spt;spt = new EdgeWeightedDigraph(V);for(int v = 0;v<V; v++)if(edgeTo[v]!=null)spt.addEdge(edgeTo[v]);EdgeWeightedCycleFinder cf;cf = EdgeWeightedCycleFinder(spt);cycle = cf.cycle();}public boolean hasNegativeCycle() { return cycle != null; }public Iterable<DirectedEdge> negativeCycle(){ return cycle; }
}