如果加权有向图不含有向环,则下面要实现的算法比Dijkstra算法更快更简单。它有以下特点:
该方法将顶点的放松与拓扑排序结合起来,首先将distTos初始化为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[]数组,因为按照拓扑排序处理不可能再次遇到已经被放松过的顶点。