最短路径（二）

Dijkstra算法
在为了寻找加权无向图中的最小生成树的Prim算法中，构造最小生成树的每一步都向这棵树中添加一条新的边。Dijkstra算法采用了类似的方法来计算最短路径树。首先将distTo[s]初始化为0，distTo[]中的其他元素初始化为无穷大。然后将distTo[]最小的非树顶点松弛并加入树中，直到所有的顶点都在树中或所有的非树顶点distTo[]都为无穷大。

在一幅含有v个顶点和e条边的加权有向图中，使用Dijkstra算法计算根结点为给定的最短路径树所需的空间与v成正比，时间与elogv成正比（最坏情况下）。

最短路径的Dijkstra算法

public class Dijikstra{
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private IndexMinPQ<Double> pq;

    public DijikstraSP(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;
        pq.insert(s, 0, 0);
        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.weighted()){
                distTo[w] = distTo[v] + e.weighted();
                edgeTo[w] = e;
                if(pq.contains(w))  pq.change(w, distTo[w]);
                else        pq.insert(w,distTo[w]);
            }
        }
    }
    public double distTo(int v)
    public boolean hasPathTo(int v)
    public Iterable<DirectedEdge> pathTo(int v)
}

---

无环加权有向图中的最短路径算法
许多应用中的加权有向图中都是不含有环的。本算法比Dijkstra算法更快，更简单的在无环加权有向图中找出最短路径，它的特点是：

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

将拓扑排序与顶点的放松结合起来，就可以得到该算法。首先将distTo[0]初始化为0，其他distTo[]元素初始化为无穷大，然后一次按照拓扑排序的顺序松弛所有顶点。

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;
        Topological top = new Topological(G);
        for( int v:top.order())
            relax(G,v);
    }
    private void relax(EdgeWeightedDigraph G,int v)
    public double distTo(int v)
    public boolean hasPathTo(int v)
    public Iterable<DirectedEdge> pathTo(int v)

---

算法应用

优先级限制下的并行任务调度问题。 给定一组需要完成的任务和每个任务需要的时间，以及一组关于任务完成的先后次序的优先级限制。在满足限制条件的前提下如何在若干相同的处理器上安排任务并在最短时间内完成任务。

解决并行任务调度问题的关键路径方法步骤如下：创建一幅无环加权有向图，其中包含一个起点s和一个终点t且每个任务都对应着两个顶点（一个起始顶点和一个终止顶点）。对于每个任务都有一条从它的起始顶点到终止顶点的边，边的权重即为任务所需要的时间。对于每条优先级限制v->w，添加一条从v的结束顶点指向w的起始顶点权重为0的边。我们还需要为每个任务添加一条从起点指向该任务的起始顶点的权重为0的边以及一条从该任务的终止顶点指向到终点的权重为0的边。这样每个任务预计开始的时间即为从起点到它的起始顶点的最长距离。

public class CPM{
    public static void main(String[] args){
        int N = StdIn.readInt();  StdIn.readLine();
        EdgeWeightedDigraph G;
        G = new EdgeWeightedDigraph(2*N+2);
        int s = 2*N, t=2*N+1;
        for(int i=0; i<N; i++){
            String[] a= StdIn.readLine().split("\\s+");
            double duration = Double.parseDouble(a[0]);
            G.addEdge(new DirectedEdge(i, i+N, duration));
            G.addEdge(new DirectedEdge(s,i,0));
            G.addEdge(new DirectedEdge(i+N,t,0)
            for(int j=1; j<a.length;j++){
                int successor = Integer.parseInt(a[j]);
                G.addEdge(new DirectedEdge(i+N, successor, 0));
            }
        }
        AcyclicLP lp = new AcyclicLP(G, s);
        StdOut.println("Start times:");
        for(int i=0;i<N; i++)
            StdOut.printf("%4d: %5.1f\n",i, lp.distTo(i));
        StdOut.printf("Finsh time:%5.1f\n",lp.distTo(t));
    }
}