给出一个无向加权图G，和两个顶点：顶点开始和结束顶点

given an undirected weighted graph G , and two vertices: start vertex and end vertex

什么是最有效的算法，发现从开始的最短路径，以结束与打开的重量只有一个边缘到零的能力？

what's the most efficient algorithm that finds the shortest path from start to end with ability to turn weight of exactly one edge to zero?

编辑： 我知道Dijkstra算法，但正如我所说， 情况是这一问题的不同：我们允许把一个边缘到零，

i know dijkstra algorithm , but as i said , situation is different in this problem: we're allowed to turn one edge to zero,

我想知道如何有效地解决这个问题， 实际上，单程被转边缘权重为零迭代！和应用的Dijkstra algorithmin每个步骤， 但是，我正在寻找更有效的方法

i wanna know how solve this problem efficiently, actually , one way is turn edges weights to zero iteratively! and apply dijkstra algorithmin each step, but , i'm looking for more efficient way

感谢

推荐答案

您可以通过使用Djikstra的算法的两倍大小的增强图形解决这个问题。

You can solve this by using Djikstra's algorithm on an augmented graph of twice the size.

假设你有个顶点为1 ...... n。

Suppose you have vertices 1...n.

定义一个新的曲线图，使得对于b相重量每个边缘A->瓦特在原始的，限定A->片b与权重w，A-> B + n，其中重量0，并且a +正>乙+ N与权重w

Define a new graph such that for each edge a->b with weight w in the original, define edges a->b with weight w, a->b+n with weight 0, and a+n->b+n with weight w.

的想法是，顶点的n + 1..n的+ n为包含原始图表的副本重复。从原来的移动到重复再presents使用特殊转向边缘为0。注意能力，一旦你在重复是没有办法恢复到原来的图形使这个特殊能力只能使用一次

The idea is that the vertices n+1..n+n are duplicates containing a copy of the original graph. Moving from the original to the duplicate represents using your special ability of turning an edge to 0. Note that once you are in the duplicate there is no way of returning to the original graph so this special ability can only be used once.

因此​​，你只需要解决的问题上，从开始去年底增加图+ N找到包括你的能力来设置单重为0的最短路径。

Therefore you just need to solve the problem on the augmented graph of going from start to end+n to find the shortest path including your ability to set a single weight to 0.