Network interdiction is a type of zero-sum game where one player (the interdictor) wants to decrease the usefulness of a network to the other (the user). This is a classic problem type in operations research, but solution methods typically resort to mixed integer programming. Khachiyan et al. (2008) consider network interdiction where the user wants to build a minimum-weight path and the interdictor can remove edges subject to vertex-local budgets. They show that optimal strategies can be efficiently computed with a modified Dijkstra's algorithm. We extend the model of Khachiyan et al. in two directions, by allowing partial interdiction of edges and various ways to define the weight of a path, and we show that efficient algorithms still exist.