最短路径

最短路径应用的图是加权有向图
加权有向图的数据结构：
首先定义的是加权有向边的数据类型：

public class DirectEdge {
	private int v;//边的起点
	private int w;//边的终点
	private double weight;//边的权重
	public DirectEdge(int v,int w,double weight){
		this.v=v;
		this.w=w;
		this.weight=weight;
	}
	public double weight(){
		return weight;
	}
	public int from(){
		return v;
	}
	public int to(){
		return w;
	}
	public String toString(){
		return String.format("%d->%d %.2f", v,w,weight);
	}
} ```

在加权有向边的基础上定义加权有向图  
```java
public class EdgeWeightDigraph {
	private int V;
	private int E;
	private Bag<DirectEdge>[] adj;
	public EdgeWeightDigraph(int V){
		this.V=V;
		this.E=0;
		adj=(Bag<DirectEdge>[])new Bag[V];
		for(int v=0;v<V;v++){
			adj[v]=new Bag<DirectEdge>();
		}
	}
	public int V(){
		return V;
	}
	public int E(){
		return E;
	}
	public void addEdge(DirectEdge e){
		int v=e.from();
		adj[v].add(e);
		E++;
	}
	public Iterable<DirectEdge> adj(int v){
		return adj[v];
	}
	public Iterable<DirectEdge> edges(){
		Bag<DirectEdge> bag=new Bag<DirectEdge>();
		for(int v=0;v<V;v++){
			for(DirectEdge e:adj[v]){
				bag.add(e);
			}
		}
		return bag;
	}
}

最短路径：从图的一个顶点到达另一个顶点的成本最小(权重和最小)的路径，这里的最短路径是单点最短路径
最短路径树： 给定一幅加权有向图和顶点s，可以找到一个以s为起点的最小路径树，他是图的一幅子图，包含了顶点s和所有s可达的顶点。树的根节点是s，树的每一条路径都是有向图中的一条最短路径

最短路径算法原理

边的松弛
Java数据结构-图(最短路径)
顶点的松弛

最短路径的最优条件：
一幅有向加权图G,顶点s为起点，distTo[]保存着起点s到任意顶点v的路径长度，若s到v不可达，该值为无穷大。当且仅当对于从v到w的任意一条边e，满足**distTo[w]<=distTo[v]+e.weight()**条件时，才是最短路径

Dijkstra算法

算法思想
1. 首先Dijkstra算法只适用在权值非负的加权有向图
  如下图所示，E(v2,v5)为负值，如果想找到v5到v4的最短路径，那么这一条路径：v5->v4->v2->v5->v4的权值之和为-6，如此一直沿着这条路径循环，那么v5到v4的路径权重之和会越来越小，趋近于负无穷，那么这两个顶点之间的最短路径无法确定。我们称图中这样的循环为负值圈，有向图中出现负值圈时，最短路径的问题就无法确定。
  
  2）Dijkstra算法的思想
  首先确定源点s，dist[v]表示的是从s到v的最短路径距离
  Dijkstra算法每次从没有确定最短路径的顶点中选择dist[]值最小的顶点v，对v的所有边进行松弛，如此操作直到确定所有顶点的最短路径
算法实现

public class Dijkstra {
	private DirectEdge[] edgeTo;
	private double[] distTo;
	private IndexMinPQ<Double> pq;
	public Dijkstra(EdgeWeightDigraph G,int s){
		edgeTo=new DirectEdge[G.V()];
		distTo=new double[G.V()];
		pq=new IndexMinPQ<Double>(G.V());
		//初始化distTo所有项为正无穷
		for(int v=0;v<G.V();v++){
			distTo[v]=Double.POSITIVE_INFINITY;
		}
		//起始点设置为0
		distTo[s]=0.0;
		//将起始点入队  
		pq.insert(s, 0.0);
		while(!pq.isEmpty()){
			relax(G,pq.deleteMin());
		}
	}
	private void relax(EdgeWeightDigraph G,int v){
		for(DirectEdge 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.changeKey(w, distTo[w]);
				}else{
					pq.insert(w, distTo[w]);
				}
			}
		}
	}
	public boolean hasPathTo(int v){
		return distTo[v]<Double.POSITIVE_INFINITY;
	}
	public double distTo(int v){
		return distTo[v];
	}
	public Iterable<DirectEdge> pathTo(int v){
		Stack<DirectEdge> stack=new Stack<DirectEdge>();
		while(edgeTo[v]!=null){
			stack.push(edgeTo[v]);
			v=edgeTo[v].from();
		}
		return stack;
	}
}

算法分析
Dijkstra算法时间复杂度取决于存储顶点的数据结构
上面算法的实现使用的是最小优先队列，每次删除最小距离顶点时间复杂度为logV，整个算法需要对每条边松弛，所以基于最小优先队列的Dijkstra算法的时间复杂度为ElogV

基于拓扑排序的最短路径算法

算法原理
将图按照拓扑排序的顺序放松顶点

这种算法只能应用在无环有向图中，并且它允许图的边的权重是负值，他还能解决相关的问题比如最长路径
算法实现

//利用拓扑排序实现的最短路径算法  
public class AcyclicSP {
	private DirectEdge[] edgeTo;
	private double[] distTo;
	public AcyclicSP(EdgeWeightDigraph G,int s){
		edgeTo=new DirectEdge[G.V()];
		distTo=new double[G.V()];
		for(int v=0;v<G.V();v++){
			distTo[v]=Double.POSITIVE_INFINITY;
		}
		distTo[s]=0.0;
		TopoEdgeWeight top=new TopoEdgeWeight(G);
		for(int v:top.order()){
			relax(G,v);
		}
	}
	private void relax(EdgeWeightDigraph G,int v){
		for(DirectEdge e:G.adj(v)){
			int w=e.to();
			if(distTo[w]>distTo[v]+e.weight()){
				distTo[w]=distTo[v]+e.weight();
				edgeTo[w]=e;
			}
		}
	}
	public boolean hasPathTo(int v){
		return distTo[v]<Double.POSITIVE_INFINITY;
	}
	public double distTo(int v){
		return distTo[v];
	}
	public Iterable<DirectEdge> pathTo(int v){
		Stack<DirectEdge> stack=new Stack<DirectEdge>();
		while(edgeTo[v]!=null){
			stack.push(edgeTo[v]);
			v=edgeTo[v].from();
		}
		return stack;
	}	
}```
在查找最短路径之前需要对图进行拓扑排序    
```java
public class TopoEdgeWeight {
	private boolean marked[];
	private Stack<Integer> stack;
	public TopoEdgeWeight(EdgeWeightDigraph G){
		marked=new boolean[G.V()];
		stack=new Stack<Integer>();
		EdgeWeightDigraphCycle cycle=new EdgeWeightDigraphCycle(G);
		if(!cycle.hasCycle()){
			TopoSort(G);
		}
	}
	private void TopoSort(EdgeWeightDigraph G){
		for(int v=0;v<G.V();v++){
			if(!marked[v]){
				dfs(G,v);
			}
		}
	}
	private void dfs(EdgeWeightDigraph G,int v){
		marked[v]=true;
		for(DirectEdge e:G.adj(v)){
			if(!marked[e.to()]){
				dfs(G,e.to());
			}
		}
		stack.push(v);
	}
	public Iterable<Integer> order(){
		return stack;
	}
}```
在拓扑排序之前需要检查图是不是无环图  
```java
public class EdgeWeightDigraphCycle {
	private boolean[] marked;
	private DirectEdge[] edgeTo;
	private Stack<DirectEdge> cycle;
	private boolean[] onStack;
	public EdgeWeightDigraphCycle(EdgeWeightDigraph G){
		marked=new boolean[G.V()];
		edgeTo=new DirectEdge[G.V()];
		onStack=new boolean[G.V()];
		for(int v=0;v<G.V();v++){
			if(!marked[v]){
				dfs(G,v);
			}
		}
	}
	private void dfs(EdgeWeightDigraph G,int v){
		marked[v]=true;
		onStack[v]=true;
		for(DirectEdge e:G.adj(v)){
			int w=e.to();
			if(hasCycle()){
				return;
			}else if(!marked[w]){
				edgeTo[w]=e;
				dfs(G,w);
			}else if(onStack[w]){
				cycle=new Stack<DirectEdge>();
				DirectEdge f=e;
				while(f.from()!=w){
					cycle.push(f);
					f=edgeTo[f.from()];
				}
				cycle.push(f);
				return;
			}
		}
		onStack[v]=false;
	}
	public boolean hasCycle(){
		return cycle!=null;
	}
	public Iterable<DirectEdge> cycle(){
		return cycle;
	}
}  ```
3. 算法分析  
基于拓扑排序的最短路径算法是一种比Dijkstra算法更快更简单的在无环加权有向图中找到最短路径的算法 
基于拓扑排序的最短路径算法的**时间复杂度是O(V+E)** 

# Floyd算法  
1. 算法原理  
	从任意节点v到节点w最短路径有两种情况：第一种是直接从v到w；第二种是从v经过若干个节点到达w，对图中的每个节点k，检查dist(v,k)+dist(k,w)<dist(v,w)是否成立，如果成立，那么更新v到w的最短路径为dist(v,k)+dist(k,w)，如此当我们遍历完图中所有的节点之后，v到w的最短路径和最短距离就确定了。  
   	此算法就是一任意的顺序放松图中所有的边，重复V轮。

2. 算法实现  
三重循环实现  
```java  
for (int k=0; k<n; ++k) {
  for (int i=0; i<n; ++i) {
    for (int j=0; j<n; ++j) {
      if (dist[i][k] + dist[k][j] < dist[i][j] ) {
        dist[i][j] = dist[i][k] + dist[k][j];
		path[i][j] = path[k][j];
      }
    }
  }
}```

3. 算法分析  
	Floyd算法的时间复杂度为：O(V3)    
   
# Bellman-Ford算法  

Bellman-ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写  
1. 算法原理  
   利用队列  
2. 算法实现  
```java
public class BellmanFord {
	private double[] distTo;
	private DirectEdge[] edgeTo;
	private boolean[] onQ;//该顶点是否在队列中
	private Queue<Integer> queue;//用于存放将被放松的顶点
	private int cont;//放松的次数
	private Iterable<DirectEdge> cycle;	
	public BellmanFord(EdgeWeightDigraph G,int s){
		distTo=new double[G.V()];
		edgeTo=new DirectEdge[G.V()];
		onQ=new boolean[G.V()];
		queue=new Queue<Integer>();
		for(int v=0;v<G.V();v++){
			distTo[v]=Double.POSITIVE_INFINITY;
		}
		queue.enqueue(s);
		onQ[s]=true;
		distTo[s]=0.0;
		while(!queue.isEmpty() && hasNegativeCycle()){
			int v=queue.dequeue();
			onQ[v]=false;
			relax(G,v);
		}
	}
	private void relax(EdgeWeightDigraph G,int v){
		for(DirectEdge 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(cont++ % G.V() ==0){
				findNegativeCycle();
			}
		}
	}
	public void findNegativeCycle(){
		int V=edgeTo.length;
		EdgeWeightDigraph bf=new EdgeWeightDigraph(V);
		for(int v=0;v<V;v++){
			if(edgeTo[v]!=null){
				bf.addEdge(edgeTo[v]);
			}
		}
		EdgeWeightDigraphCycle cf=new EdgeWeightDigraphCycle(bf);
		cycle=cf.cycle();
	}
	public boolean hasNegativeCycle(){
		return cycle!=null;
	}
	public Iterable<DirectEdge> negativeCycle(){
		return cycle;
	}
	public boolean hasPathTo(int v){
		return distTo[v]<Double.POSITIVE_INFINITY;
	}
	public double distTo(int v){
		return distTo[v];
	}
	public Iterable<DirectEdge> pathTo(int v){
		Stack<DirectEdge> stack=new Stack<DirectEdge>();
		while(edgeTo[v]!=null){
			stack.push(edgeTo[v]);
			v=edgeTo[v].from();
		}
		return stack;
	}	
}

算法分析
BellmanFord算法的时间复杂度一般情况为O(E+V),最坏情况为O(VE)

参考：《算法第四版》

Java数据结构-图(最短路径)

最短路径

最短路径算法原理

Dijkstra算法

基于拓扑排序的最短路径算法

相关推荐