2018-09-02

图论——最短路径

阅读此篇之前，需要了解图论的基础知识、拓扑排序、最小生成树。

最短路径的最直观应用就是在地图导航中，路口对应顶点，公路对应边，如果是单行道对应有向边，公路长短对应权重。抽象模型来看，就是从一个顶点到另一个顶点的最小成本路径——单点最短路径。

问题模型定义：

边是有向的。（区别于最小生成树）

边的权重不一定表示距离，更合适的应称为成本。（可以表示很多意义）

边的权重为负会比较复杂，我们最后讨论为负的情况。

最短路径都是简单路径。（不含有环）

最短路径不唯一。

可能存在自环或平行边。（分析时不考虑，算法可以处理）

最短路径表示的是任意顶点v到起点s的权重都是最短路径，而最小生成树是顶点v到树的权重最小，两者要分清楚。

数据模型

处理最短路径问题，需要加权有向边构成的加权有向图作为数据结构基础。

加权有向边

与Edge相比，把边的两个顶点重新明确为from()到to()，用以表示边的方向。

DirectedEdge 加权有向边DirectedEdge.java

public class DirectedEdge implements Comparable<DirectedEdge> {
    ···
    private final int v;            //边的起点
    private final int w;            //边的终点

    public int from() {
        return v;
    }

    public int to() {
        return w;
    }
    ···
}

加权有向图

与加权无向图EdgeWeightedGraph相比，将图中的边替换为加权有向边DirectedEdge，再稍作修改addEdge()即可。

EdgeWeightedDigraph 加权有向图EdgeWeightedDigraph.java

public class EdgeWeightedDigraph {
    private final int V;                //顶点
    private int E;                      //边
    private Bag<DirectedEdge>[] adj;    //邻接表

    public EdgeWeightedDigraph(int V) {
        this.V = V;
        E = 0;
        adj = (Bag<DirectedEdge>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<>();
    }

    public void addEdge(DirectedEdge edge) {
        adj[edge.from()].add(edge);
        E++;
    }

    public Iterable<DirectedEdge> adj(int v) {
        return adj[v];
    }

    public Iterable<DirectedEdge> edges() {
        Bag<DirectedEdge> bag = new Bag<>();
        for (int v = 0; v < V; v++)
            for (DirectedEdge edge : adj[v])
                bag.add(edge);
        return bag;
    }
    ···
}

最短路径操作原理

最短路径需要的数据结构很简单：

最短路径树的边edgeTo[]。
到达起点的距离distTo[]。

松弛

与最小生成树的Prim即时算法类似，在每次添加边的时候，会对原有的路径进行权重对比，如果出现更小的路径，则替换当前路径。这个操作就是松弛

relax(edge) 对边的放松

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

在实际的实现中，实现松弛会放松relax()一个给定顶点指出的所有边。

relax(v) 对顶点的放松

private void relax(EdgeWeightedDigraph G, int v) {
    for (DirectedEdge edge : G.adj(v)) {
        int w = edge.to();
        if (distTo[w] > distTo[v] + edge.weight()) {
            distTo[w] = distTo[v] + edge.weight();
            edgeTo[w] = edge;
        }
    }
}

Dijkstra算法

边的权重不能为负！

对于实现算法，我们仍需要IndexMinPQ<T>来保存即将被放松的顶点。算法的实现非常相似于Prim算法的即时实现，仅仅是替换为加权有向图来表示。

证明请查看Prim算法。

DijkstraSP Dijkstra算法DijkstraSP.java

public class DijkstraSP {
    ···
    private DirectedEdge[] edgeTo;
    private IndexMinPQ<Double> pq;

    public DijkstraSP(EdgeWeightedDigraph G, int s) {
        ···
        distTo[s] = 0.0;
        pq.insert(s, distTo[s]);
        while (!pq.isEmpty())
            relax(G, pq.delMin());
    }

    private void relax(EdgeWeightedDigraph G, int v) {
        if (v < 0 || v >= distTo.length) throw new NoSuchElementException("vertex is illegal!");
        for (DirectedEdge edge : G.adj(v)) {
            int w = edge.to();
            if (distTo[w] > distTo[v] + edge.weight()) {
                distTo[w] = distTo[v] + edge.weight();
                edgeTo[w] = edge;
                if (pq.contains(w)) pq.changeKey(w, distTo[w]);
                else pq.insert(w, distTo[w]);
            }
        }
    }
    ···
}

性能

空间：V
时间：ElogV

给定两点之间的最短路径

直接用Dijkstra算法就可以，s->t，从起点s开始relax，直到优先队列取到t为止即可。

任意顶点对之间的最短路径

可以将每个元素都作为顶点构造DijkstraSP对象。

性能：时间和空间均与 EVlogV 成正比。

点击查看算法实现。

无环加权有向图中的最短路径算法

通过拓扑排序来构成数据结构，按照拓扑排序的顺序依次放松各个顶点。

算法优点

能够在线性时间内处理单点最短路径问题。
能够处理负权重边的情况。
能够处理最长路径问题。

算法实现

这里需要Topological拓扑排序接受EdgeWeightedDigraph和DirectedEdge为参数，检测有向环以及构建数据结构。寻找有向环的算法实现

AcyclicSP由Dijkstra算法改编而来，仅仅修改了初始化时放松顶点的顺序即可。

AcyclicSP 无环加权有向图的最短路径算法AcyclicSP.java

public class AcyclicSP {
    ···
    public AcyclicSP(EdgeWeightedDigraph G, int s) {
        ···
        Topological top = new Topological(G);
        for (int v : top.order())
            relax(G, v);
    }
    ···
}

性能

性能：
时间：E+V，线性

无环加权有向图中的最长路径算法

通过最短路径改编即可，算法实现AcyclicLP：

将所有边clone()得到副本，再将副本的权重取相反数，即可。
将distTo[]初始赋值变为Double.NEGATIVE_INFINITY，并改变relax()中判断不等式的方向，即可。

优先级限制下的并行任务调度

拓扑排序相对来说只是单个处理器执行问题处理，而并行任务调度则是多个处理器同时处理问题。

这个问题其实是求解最长路径的问题。（木桶短板效应）

性能：线性

关键路径

解决此类问题的算法称为关键路径，实现步骤如下：

创建无环加权有向图。
所有任务的起始为起点s，指向每个先行任务的开始，终点为t，每个最后执行任务的结束指向t。
任务作为边，边的权重为每个任务的花费时间，优先级v -> w为任务的结束点指向下一个任务的起始点。
每个任务预计的花费时间为任务自身的权重加上任务起点距离起点s的权重。这样就转化为最长路径的问题。

CPM 关键路径的一种实现CPM.java

public class CPM {
    public static void main(String[] args) {
        int N = StdIn.readInt();
        StdIn.readLine();
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(2 * N + 2);
        int s = N * 2, t = N * 2 + 1;//s起点，t终点，0~2N所有顶点
        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.0));
            G.addEdge(new DirectedEdge(i + N, t, 0.0));
            for (int j = 1; j < a.length; j++) {
                int successor = Integer.parseInt(a[j]);
                G.addEdge(new DirectedEdge(i + N, successor, 0.0));
            }
        }
        AcyclicLP lp = new AcyclicLP(G, s);
        System.out.println("Start times:");
        for (int i = 0; i < N; i++)
            System.out.printf("%d: %5.1f\n", i, lp.distTo(i));
        System.out.printf("Finish time: %5.1f\n", lp.distTo(t));
    }
}

相对最后期限限制下的并行任务调度

其实这是一个最短路径问题。

一般加权有向图中的最短路径

此时我们需要探讨负权重边带来的情况。

负权重环，指一个总权重之和为负的环。

一旦出现负权重环，则不存在最短路径。

因为可以在负权重环中无限循环从而产生任意小的最短路径。因此我们需要s到v的有向路径上的任意顶点都不存在于任何负权重环中。

于是实现算法需要解决以下问题：

负权重环的检测。
负权重环不可达时的最短路径问题。

Bellman-Ford算法

检测负权重环

类似于之前拓扑排序中寻找有向环的检测，我们这里也用一个onQ[]来记录顶点是否在放松过的栈上，防止重复加入队列。

relax(G,v) Bellman-Ford中检测负权重环

private void relax(EdgeWeightedDigraph G, int v) {
    for (DirectedEdge edge : G.adj(v)) {
        int w = edge.to();
        if (distTo[w] > distTo[v] + edge.weight()) {
            distTo[w] = distTo[v] + edge.weight();
            edgeTo[w] = edge;
            if (!onQ[w]) {
                queue.enqueue(w);
                onQ[w] = true;
            }
        }
        if (cost++ % G.V() == 0)
            findNegativeCycle();//周期性寻找负权重环
    }
}

寻找负权重环

这里采用EdgeWeightedDirectedCycle(最短路径中拓扑排序)来检测加权有向环。

findNegativeCycle() 寻找负权重环

public void findNegativeCycle() {
    int V = edgeTo.length;
    EdgeWeightedDigraph spt;
    spt = new EdgeWeightedDigraph(V);
    for (DirectedEdge edge : edgeTo)
        if (edge != null)
            spt.addEdge(edge);
    EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
    cycle = finder.cycle();
}

算法实现

BellmanFordSP 基于队列的Bellman-Ford算法BellmanFordSP.java

public class BellmanFordSP {
    private double[] distTo;                //从起点到某个顶点的路径长度
    private DirectedEdge[] edgeTo;          //从起点到某个顶点的最后一条边
    private boolean[] onQ;                  //该顶点是否存在于队列中
    private Queue<Integer> queue;           //正在被放松的顶点
    private int cost;                       //relax() 的调用次数
    private Iterable<DirectedEdge> cycle;   //edgeTo[] 中是否还有负权重环

    public BellmanFordSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        onQ = new boolean[G.V()];
        queue = new Queue<>();
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;
        onQ[s] = true;
        while (!queue.isEmpty() && !hasNegativeCycle()) {
            int v = queue.dequeue();
            onQ[v] = false;
            relax(G, v);
        }
    }

    private void relax(EdgeWeightedDigraph G, int v) {
        ···
    }

    public void findNegativeCycle() {
        ···
    }

    public Iterable<DirectedEdge> negativeCycle() {
        return cycle;
    }

    public boolean hasNegativeCycle() {
        return cycle != null;
    }
    ···
}

性能

空间：V
时间：EV（放松E条边，重复V轮）

本文标题:图论——最短路径

文章作者:

发布时间:2018-09-02, 20:16:23

最后更新:2020-09-12, 16:12:15

原始链接:http://yif-hong.github.io/2018/09/02/Graph-SP/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。