最短路径定义。 在一幅加权的有向图中，从顶点s到顶点t的最短路径是所有从s到t的路径中的权重最小者。
最短路径树定义。 给定一幅加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一幅子图，它包含s和从s可到达的所有顶点。这棵树的根结点为s，树的每条路径都是有向图中的一条最短路径。
加权有向图的数据结构
//加权有向边的API
public class DirectedEdge
DirectedEdge(int v, int w, double weight)
double weight() //边的权重
int from() //指出这条边的顶点
int to() //指出这条边指向的顶点
String toString() //对象的字符串表示
//加权有向图的API
public class EdgeWeightedDigraph
EdgeWeightedDigraph(int v) //含有v个顶点的空有向图
EdgeWeightedDigraph(In in) //从输入流读取图的构造函数
int V() //顶点总数
int E() //边的总数
void addEdge(DirectedEdge e) //将e添加到该有向图中
Iterable<DirectedEdge> adj(int v) //从v指出的边
Iterable<DirectedEdge> edges() //该有向图中的所有边
String toString() //对象的字符串表示
以下代码为加权有向边和图的具体实现
public class DirectedEdge{
private final int v; //边的起点
private final int w; //边的终点
private final 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 from(){
return v;
}
public int to(){
return w;
}
public String toString(){
return String.format("%d->%d %.2f", v, w, weight);
}
}
public class EdgeWeightedDigraph{
private final int V; //顶点总数
private int E; //边的总数
private Bag<DirectedDigraph>[] 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 EdgeWeightedDigraph(In in)
public int V(){ return V; }
public int E(){ return E; }
public void addEdge(DirectedEdge e){
adj[e.from()].add(e);
E++;
}
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;
}
最短路径API
public class SP
SP(EdgeWeightDigraph G, int s) //构造函数
double distTo(int v) //从顶点s到v的距离，如果不存在则路径为无穷大
boolean hasPathTo(int v) //判断是否存在从s到v的路径
Iterable<DirectedEdge> pathTo(int v) //从顶点s到v的路径，如果不存在则为null
最短路径的数据结构
- 最短路径树中的边。 和深度优先算法，广度优先算法和Prim算法一样，使用一个由顶点索引的DirectedEdge对象的父链接数组edgeTo[]，其中edgeTo[v]的值为树中连接v和它的父结点的边（也是从s到v的最短路径上的最后一条边）。
- 到达起点的距离。 我们需要一个由顶点索引的数组distTo[]，其中distTo[v]为从s到v的已知最短路径的长度。
边的松弛
我们的最短路径API的实现都基于一个被称为松弛的操作。一开始，distTo[]中只有起点所所对应的元素的值为0，其余元素的值均被初始化为Double.POSITIVE_INFINITY。随着算法的执行，它将起点到其他顶点的最短路径信息存入edgeTo[]和distTo[]数组中。在遇到新的边时，通过更新这些信息就可以得到新的最短路径，这其中就会用到边的松弛技术——松弛v->w意味着检查从s到w的最短路径是否是先从s到v，然后再从v到w。如果是，则根据这个情况更新数据结构的内容。
private void relax(DirectedEdge e){
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()){
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
上面的代码实现了松弛的操作。由v到w的最短路径是distTo[v]与e.weight()之和，如果这个值不小于distTo[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;
}
}
}
这个方法的实现会放松从一个给定顶点指出的所有边。某点从起点指出的边将会是第一条被加入edgeTo[]中的边。算法会谨慎的选择顶点，使得每次顶点的松弛操作都能得出到达某个顶点的更短的路径，最后逐渐找出到达每个顶点的最短路径。
查询方法
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 = edge=edgeTo[v]; e!=null; e=edgeTo[e.from()])
path.push(e);
return path;
}
