Estimating the criticality of each link in a transportation network is a crucial step for guiding the design and deployment of vulnerability reduction measures. Using exhaustive simulations based on user-equilibrium assignment to evaluate the effect of the failure of each link (or set of links) can be prohibitively time-consuming for reasonably-sized transportation networks. In this paper, we propose an alternative heuristic approach to the estimation the vulnerability of network links employing efficient graph-theoretical algorithms. In particular, our model estimates the cost of single link failure based on the increase in shortest path travel time taking into account the effect of congestion. Results show that the proposed method can reliably be used to estimate the relative effect of each link failure on the system travel time and rank links accordingly. © 2011 IEEE.