2
$\begingroup$

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)?

$\endgroup$

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.