8

我有这个问题：“具有一条可跳过边的最短路径。给定一个边加权有向图，设计一种E*log(V)算法来找到一条最短路径，从s那里t您可以将任何一条边的权重更改为零。假设边权重是非负的。 "

我不明白他们要我做什么。将权重更改为零是什么意思？我认为我可以将任何最短路径中的任何边缘更改为零，它仍然是最短的。

4

5 回答 5

10

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

注意：在这种方法中，我们使边缘(v,w)权重无效并找到通过的最短路径(v,w)

于 2013-04-30T09:49:50.667 回答
5

问题很简单。

假设你有一条最短路径，有一条可跳过的边，p = v1,...,vi,vi+1,...,vm 并且 (vi,vi+1) 是一条跳过的边
显然，一条路径(v1, ...,vi) 是 v1 和 vi 之间的最短路径，
而 path(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)

于 2013-04-30T10:05:01.787 回答
4

之前的答案似乎假设 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) 要跳过的是边缘 e(v1 --> v2)，其中 T(v1) + R(v2) 是最小值。

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

于 2013-11-20T10:33:19.597 回答
3

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

  1. 创建图形的副本G，然后调用它G'
  2. 对于 中的每条边(u, v)，G创建一条(u, v')从u(in G) 指向v'(in G') 的边，其权重为0。
  3. 使用任何标准最短路径算法（例如 Dijkstra）来计算从s到的最短路径t'。
于 2018-12-11T12:37:46.163 回答
1

我在 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;
        }
    }

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

其余的是非常标准的 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);因此我们不应该遇到空父边。

我认为这应该可行，除非有什么我没有想到的。

于 2019-07-26T02:15:52.427 回答