This paper deals with a mathematical model and an algorithm for the problem of determining k most vital arcs in the shortest path problem. First, we propose a 0–1 integer programming model for finding k most vital arcs in shortest path problem given the ordered set of paths with cardinality q. Next, we also propose an algorithm for finding k most vital arcs in the shortest path problem which uses the 0–1 integer programming model and shortest path algorithm and maximum flow algorithms repeatedly. Malik et al. proposed a non-polynomial algorithm to solve the problem, but their algorithm was contradicted by Bar-Noy et al. with a counter example to the algorithm in 1995. But using our algorithm, the exact solution can be found directly from the algorithm of Malik et al.
