shortest path with one edge turn to zero

问题:

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?

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

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

thanks

回答1:

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

Suppose you have vertices 1...n.

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.

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.

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.

回答2:

Dijkstra's algorithm is commonly used to solve these types of problems. Also, this sounds a bit like the TSP problem, I could be wrong on that part though.