Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed to ignore the weight (i.e. set to $0$) of at most $k$ edges on the path?

An $O(kn\log(kn)+km)$ homework-level solution will be copy the graph $k$ times and use dijkstra. But is there any better algorithm (or lower bound)?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.