logo标签列表

仅跳过一条边的最短路径

graphshortest-path
8
我有一个问题："一条可跳过边的最短路径"。给定一个带权有向图，设计一个E*log(V)算法，以查找从s到t的最短路径，其中可以将任何一条边的权重更改为零。假设边的权重为非负数。
我不明白他们想让我做什么。将权重更改为零是什么意思？我认为我可以将最短路径中的任何一条边更改为零，它仍将是最短的。
2
"我认为我可以将最短路径中的任何边改为零，仍然保持最短。" - 想象一条连接起点和终点的单个边，权重为9999999。 - BlueRaja - Danny Pflughoeft
什么意思？如果我有一条最短路径，并将这条巨大的边改为零，那么这条边会变成新的最短路径吗？ - mosceo
2
是的，这正是我想表达的意思。所以问题并不像“找到最短路径并删除其中最长的边”那样简单。也不是简单地从图中删除最长的边。我需要花些时间思考如何解决这个问题。 - BlueRaja - Danny Pflughoeft
5个回答
11
首先使用 Dijkstra 算法，对每个顶点 v 找到从 s 到 v 的最短路径长度 S(v)。然后再使用 Dijkstra 算法，对每个顶点 v 找到从 v 到 t 的最短路径长度 T(v)。然后对于每条边 (v, w)，使用上述规则计算出 S(v) + T(w) 的总和。最后选择最小路径。
注意：在此方法中，我们将边 (v,w) 的权重归零，并找到通过 (v,w) 的最短路径。
算法是否总是有效？考虑将边（u，v）设置为0。现在，如果从T到v的最短路径经过这条边会怎么样？例如，在此图中。http://imgur.com/QTAWr25 您的算法是否有效？源= 1，目标= 4，Edgeu-v =从2到3的边。 - Nikunj Banka
我相信它可以工作，但是我不理解你的例子，因为根本没有从源到目标的路径。 - Bartosz Marcinkowski
@BartoszMarcinkowski 只是为了补充你的答案，我们可以通过要求OP使用任何最短路径算法来进行概括，而不是特定地使用Dijkstra算法。 - Shubham Mittal
@BartoszMarcinkowski "然后使用Dijkstra算法查找每个顶点v到t的最短路径长度T(v)" - 这难道不会使得该算法的复杂度变为O(V * E * logV)吗？因为算法需要在每个顶点上运行Dijkstra算法。 - user1559897
1
@user1559897 不需要为每个顶点运行Dijkstra算法，只需要为两个顶点s和t运行即可。 - Bartosz Marcinkowski
6
之前的回答似乎认为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之间的最短路径连接而成。
感谢 @Marco Altieri https://raw.githubusercontent.com/Himanshu-Tamrakar/algorithms/master/src/chapter4/section4/solutions/SkippableEdgeSP.java - Himanshu Tamrakar
5
问题很简单。

假设你有一条可以跳过一条边的最短路径，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)
现在我们必须逐个选择被跳过的边。
换句话说，具有一个可跳过的边的最短路径的长度为

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

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

1
虽然另一个答案先出现并且说了同样的话，但是这个更加好地解释了。+1！ - BlueRaja - Danny Pflughoeft
4
现有的答案都很好，也是正确的，但更符合我的直觉的另一个想法是将图形转换并使用分层方法：
  1. 创建图 G 的副本，并将其称为 G'
  2. 对于图 G 中的每条边 (u, v)，创建一条从 u（在 G 中）指向 v'（在 G' 中）的带权重 0 的边 (u, v')。
  3. 使用任何标准最短路径算法，如 Dijkstra 算法，计算从 s 到 t' 的最短路径。
绝对最佳答案！ - user1559897
如何论证该算法的正确性？ - binit92
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;
        }
    }

“longest here”代表最短路径中已知的最长线段。

其余部分基本上是标准的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);，因此我们不应该遇到空的父边。
我认为这应该有效，除非有我没有考虑到的事情。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接