首页 > 代码库 > 算法8-8:最短路径性质

算法8-8:最短路径性质

在计算最短路径之前,往往会先计算最短路径树,也就是计算从一个顶点出发,到其余所有顶点的最短距离。


有了最短路径树之后,路径和距离就非常容易实现了:

public double distTo(int v) {
    return distTo[v];
}
 
public Iterable<DirectedEdge> pathTo(int v) {
    Stack<DirectedEdge> result = new Stack<DirectedEdge>();
    DirectedEdge edge = edgeTo[v];
    while (edge != null) {
        result.add(edge);
        edge = edgeTo[edge.from()];
    }
    return result;
}


“放松”操作


在最短路径算法中需要一种操作,这种操作称之为“放松”操作,目标就是让权重更小的边替代当前已知的最小边。它的代码实现如下:

private void relax(DirectedEdge edge) {
    int v = edge.from();
    int w = edge.to();
    if(distTo[w] > distTo[v] + edge.weight()) {
        distTo[w] = distTo[v] + edge.weight();
        edgeTo[w] = edge;
    }
}


实现方法


最基本的实现方法就是“放松”所有的边,得到一个最短路径树。


那么按照哪种顺序放松所有的边呢?这里有这些方法:

  • Dijkstra算法,适合非负权图

  • 拓扑排序算法,适合无环图

  • Bennman-Form算法,适合无负环图