SP Assignment

👉 题目资料链接
👉 代码

1、三个问题

Q1. Monotonic shortest path - 单调最短路径

给定一个有 E 条边的边加权有向图 G，已知起点 s，找到从 s 到其他每个顶点的 单调最短路径。一条路径上每个边缘的权重严格增加或严格减少，则该路径是单调的。要求时间复杂度是 O(ElogE)。

题干对于图的限制没有明确说明。但是从复杂度约束 O(ElogE) 来看，可以判断以 Dijkstra 算法为基础。因此我们这里就假设是无负边的图。
那么直接 Dijkstra 更新最小距离的部分加一个判断-当前边和上一条边的权重比较是否单调即可。这里用到了 algs4 中的 DirectedEdge、EdgeWeightedDigraph、IndexMinPQ 等类。

A: 在 relax() 时，更新 distTo[] 同时比较单调性。先递增查询一次，再递减查询一次。关键 code 如下： int 变量 ascend 用 1 或 -1 表示单调方向。完整代码 👉 code

private void relax(EdgeWeightedDigraph G, int v, int ascend) {
    for (DirectedEdge e : G.adj(v)) {
        int w = e.to();
        DirectedEdge lastEdge = edgeTo[v];
        if (lastEdge == null || (e.weight() * ascend > lastEdge.weight() * ascend) && distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            if (pq.contains(w)) pq.changeKey(w, distTo[w]);
            else pq.insert(w, distTo[w]);
        }
    }
}

参考资料：

Find a monotonic shortest path in a graph in O(ElogV)

Q2. Second shortest path - 次短路径

给定一个加权有向图，令 P 为从顶点 s 到顶点 t 的最短路径。设计一个 Elog(V) 的算法，以查找从 s 到 t 的除 P 以外最短的路径（不局限于简单路径）。这里假设所有边缘权重严格为正。

无负边使问题简单很多。由于给出了最短路径 P，求第二短的路径，在图中将 P 中最后一条指向 t 的边去掉后，再使用 Dijkstra 算法求解最短路径即可。对于两点之间的路径，当优先队列中加入节点 t 时即可停止。同样这里用到了 algs4 中的 DijkstraSP 等类。

A: 关键 code 如下。使用一个变量 delEdge 保存最短路径中到达节点 t 的边。去掉该边，再次寻找 s-t 的最短路径。若客户端没有给出最短路径，可以先运行一遍 Dijkstra 找出。最关键是找到需要去掉的边。完整代码 👉 code

public class SecondSP {
    private int s, t;
    private double distTo[];
    private DirectedEdge[] edgeTo;
    private IndexMinPQ<Double> pq;
    private DirectedEdge delEdge;

    public SecondSP(EdgeWeightedDigraph G, Stack<DirectedEdge> P, int s, int t) {
            this.s = s;
            this.t = t;
            int V = G.V();
            edgeTo = new DirectedEdge[V];
            distTo = new double[V];
            for (int v = 0; v < V; v++) {
                distTo[v] = Double.POSITIVE_INFINITY;
            }
            distTo[s] = 0.0;
            pq = new IndexMinPQ<>(V);
            while (!P.isEmpty()) {
                delEdge = P.pop();
            }
            pq.insert(s, 0.0);
            while (!pq.isEmpty()) {
                int v = pq.delMin();
                if (v == t) break; // 遍历到点 t 即结束
                relax(G, v);
            }

    }

    private void relax(EdgeWeightedDigraph G, int v) {
        for (DirectedEdge e : G.adj(v)) {
            if (e == delEdge) continue; //去掉 delEdge 边，relax()中唯一添加的一句
            int w = e.to();
            if (distTo[w] > distTo[v] + e.weight()) {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                if (pq.contains(w)) pq.changeKey(w, distTo[w]);
                else pq.insert(w, distTo[w]);
            }
        }
    }
}

Q3. Shortest path with one skippable edge - 拥有一条可跳过的边的最短路径

给定一个加权有向图，设计一个 O(ElogV) 算法以找到从 s 到 t 的最短路径，可以将其中任何一条边的权重改为 0。假设边的权重都是非负的。

不是很理解这题意思。这题直接看的 solution：计算从 s 到其他每个顶点的最短路径，再计算从每个顶点到 t 的最短路径。对于每个边 e=(v, w)，计算从 s 到 v 的最短路径的长度与从 w 到 t 的最短路径的长度之和。总和最小的路径即为解。按照 solution 的意思：将图中任意一条边权重改为 0，那会产生 e 个新的图，求这 e 个图里 s-t 的最短路径。那么还是要用到 algs4 中的 DijkstraSP 类。之后简单遍历寻找即可。

A: 代码如下，用一个 DijkstraSP 数组保存每个节点的最短路径树。再按照 Solution 判断即可。需要用一个 Iterable 的变量保存最后的路径。

public class EdgeSkippableSP {
    private DijkstraSP[] sps; // 储存每个点到其他所有点的最短路径
    private double minPathWeight;
    private Queue<DirectedEdge> skippableSP;

    public EdgeSkippableSP(EdgeWeightedDigraph G, int s, int t) {
        sps = new DijkstraSP[G.V()];
        skippableSP = new Queue<>();
        for (int v = 0; v < G.V(); v++) {
            sps[v] = new DijkstraSP(G, v);
        }
        minPathWeight = Double.POSITIVE_INFINITY;
        DirectedEdge minE = null;
        for (DirectedEdge e : G.edges()) {
            int v = e.from(), w = e.to();
            // 按照边来遍历： skip掉该边长，路径是否最短
            if (sps[s].distTo(v) + sps[w].distTo(t) < minPathWeight) {
                minPathWeight = sps[s].distTo(v) + sps[w].distTo(t);
                minE = e;
            }
        }
        for (DirectedEdge e : sps[s].pathTo(minE.from())) {
            skippableSP.enqueue(e);
        }
        skippableSP.enqueue(minE);
        for (DirectedEdge e : sps[minE.to()].pathTo(t)) {
            skippableSP.enqueue(e);
        }
        minPathWeight += minE.weight();
    }

    public Iterable<DirectedEdge> getPath() {
        return skippableSP;
    }

    public double getMinPathWeight() {
        return minPathWeight;
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        int s = 0, t = 2;
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
        EdgeSkippableSP sp = new EdgeSkippableSP(G, s, t);
        if (sp.getPath() != null) {
            StdOut.printf("%d to %d (%.2f)  ", s, t, sp.getMinPathWeight());
            for (DirectedEdge e : sp.getPath()) {
                StdOut.print(e + "   ");
            }
            StdOut.println();
        } else {
            StdOut.printf("%d to %d         no path\n", s, t);
        }

    }

hello world

关于最短路径（SP）的三个小问题