Modified Shortest Path Problem

Consider a directed, weighted graph $G=(V, E)$ where all edge weights are positive. You have one magic star, which lets you traverse one edge of your choice for free. In other words, you may change the weight of any one edge in $G$ to zero.

You are given two distinct vertices $s$ and $t$ in $G$. Give an efficient algorithm to find a lowest cost path between vertices $s$ and $t$ given that $G$ is in adjacency list format.

My first attempt involves collecting all paths between $s$ and $t$, then for each path, finding the total path weight and the highest weighted edge. I can then find the smallest path weight after subtracting the highest weighted edge from each path. This seems inefficient, is there a better way?

• Something just slightly more efficient than a brute-force approach would be to calculate all-pairs shortest paths and then for each edge $e = (u,v)$ calculate $s \to u \xrightarrow{e} v \to t$. There are some special cases, but nothing hard. Dec 3, 2013 at 18:37

Create a new graph $H$ which consists of two copies of graph $G$ (think of them being one over top of the other). The edges are the edges in $G$ in each copy, plus a directed edge of weight $0$ from the bottom copy of $u$ to the top copy of $v$ whenever $(u,v)$ is an edge in $G$; taking such an edge is using the magic star. Now apply Dijkstra from the bottom copy of $s$ to the top copy of $t$. With standard data structures this takes $O(|E|\log|V|)$ time.