一条可跳过边的最短路径

Question

我有这个问题:"具有一个可跳过边的最短路径。给定一个边加权有向图，设计一个E*log(V)算法来找到从s到t的最短路径，在该路径中可以将任意一条边的权值更改为零。假设边权是非负的。"

我不明白他们要我做什么。将权值变为0意味着什么?我想我可以把最短路径上的任何一条边都改成0它仍然是最短的

Answer 1

首先用Dijkstra求每个顶点v从s到v的最短路径的长度S(v)。然后用Dijkstra求出每个顶点v从v到t的最短路径长度T(v)。然后对每条边(v, w)，用上面的规则求和S(v) + T(w)。最后，选择最小路径。

注意:在这种方法中，我们取消(v,w)边的权值，并找到通过(v,w)的最短路径

Answer 2

问题很简单。

假设你有一条有一条可跳过边的最短路径，p = v1，…，vi,vi+1，…，vm(vi,vi+1)是跳过的边
显然，路径(v1，…，vi)是v1和vi之间的最短路径
路径(vi+1，…，vm)是vi+1到vm的最短路径
定义d(x,y)为节点x到节点y之间最短路径的长度
通过dijkstra算法可以简单地找到所有节点x的d(s,x)和d(x,t)现在我们要一条一条地选择跳过的边。换句话说，具有一条可跳过边的最短路径的长度为

对于图中所有边(u,v)的min(d(s,u) + d(v,t))

，由于Dijkstra算法，时间复杂度为O(E log V)

Answer 3

前面的答案似乎假设Dijkstra给出了从每个顶点到每个顶点的最短距离，但事实并非如此。

如果你只执行一次Dijkstra，从s开始，你就得到了从s到每个顶点的最短路径。

为了找到从每个顶点到t的最短距离，需要在反转图的每条边后从t开始再次执行Dijkstra。

完整的解决方案是:

1)对从s开始的图G执行Dijkstra，求s到任意v的最短距离T(v)

2)反转所有边得到反转图G'

3)从t开始对图G'执行Dijkstra，求出t到任意v的最短距离R(v)

4)要跳过的边是T(v1) + R(v2)最小的边e(v1 -> v2)。

5)要遵循的路径是第一个Dijkstra给出的s到v1之间的最短路径和第二个Dijkstra给出的v2到t之间的最短路径的串联。

Answer 4

现有的答案是好的和正确的，但对我来说另一个更直观的想法是转换图形并使用分层方法:

1. 创建图形G的副本，并命名为G'
2. 对于G中的每条边(u, v)，创建一条从u (G)到v' (G')的边(u, v')，权值为0。
3. 使用任何标准的最短路径算法，如Dijkstra，计算s到t'的最短路径。

Answer 5

我在Coursera上普林斯顿算法课程时遇到了这个问题。我得到了公认的答案，但我想到了一个方法，我认为它应该提供从s到任何其他边的最短路径，其中有一条跳过的边。

我们将使用下面的类来存储加权的有向边信息:

public class DirectedEdge implements Comparable<DirectedEdge> {
    private int from;
    private int to;
    private double weight;
    ... boilerplate stuff...

但是，我们还将添加一个装饰器类:

public static class SkipPathEdge {
        DirectedEdge directedEdge;
        double longest;
        public SkipPathEdge(DirectedEdge directedEdge, double longest) {
            this.directedEdge = directedEdge;
            this.longest = longest;
        }
    }

这里的longest表示到达顶点的已知最短路径的已知最长段。

其余的是非常标准的Djikstra的索引最小优先级队列，但有一个稍微修改的松弛方法:

private void relax(EdgeWeightedDigraph G, int e) {
        SkipPathEdge parentEdge = edgeTo[e];
        for (DirectedEdge edge : G.adj(e)) {
            double longest = Math.max(parentEdge.longest, edge.getWeight());
            double adjustment = longest - parentEdge.longest;
            SkipPathEdge childEdge = new SkipPathEdge(edge, longest);
            int from = edge.getFrom(), to = edge.getTo();
            if (distTo[to] > distTo[from] + edge.getWeight() - adjustment) {
                distTo[to] = distTo[from] + edge.getWeight() - adjustment;
                edgeTo[to] = childEdge;
                if (minPQ.contains(to)) {
                    minPQ.changeKey(to, distTo[to]);
                } else {
                    minPQ.addKey(to, distTo[to]);
                }
            }
        }
    }

为了澄清，我们将edgeTo[s]初始化为new SkipPathEdge(null, 0);，所以我们不应该遇到空父边。

我认为这应该工作，除非有什么我没有想到。