最短的路径,一个可跳过的边缘

Question

我有这样的问题:" 有一个可跳过的边缘最短路径.给定一个边加权有向图,设计一个E*log(V)算法找到最短路径s,以t在那里你可以改变任何一个边缘到零的重量假设边的权都是非负的. "

我不明白他们要我做什么.将重量变为零意味着什么？我认为我可以将任何最短路径中的任何边缘改为零,它仍然是最短的.

Answer 1

先用Dijkstra算法寻找长度S(v)从最短路径s来v为每个顶点v.然后使用Dijkstra算法查找长度T(v)从最短路径v来t为每个顶点v.然后,对于每个边缘,使用上面的规则(v, w)找到总和S(v) + T(w).最后,选择最小路径.

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

Answer 2

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

如果从 s 开始仅执行 Dijkstra 一次，则您将获得从 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 3

问题很简单。

假设您有一条具有一条可跳过边的最短路径，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）