Inspired by the Elitzur-Vaidman bomb testing problem [arXiv:hep-th/9305002], we introduce a new query complexity model, which we call bomb query complexity \(B(f)\). We investigate its relationship with the usual quantum query complexity \(Q(f)\), and show that \(B(f)=\Theta(Q(f)^2)\). This result gives a new method to upper bound the quantum query complexity: we give a method of finding bomb query algorithms from classical algorithms, which then provide nonconstructive upper bounds on \(Q(f)=\Theta(\sqrt{B(f)})\). We subsequently were able to give explicit quantum algorithms matching our upper bound method. We apply this method on the single-source shortest paths problem on unweighted graphs, obtaining an algorithm with \(O(n^{1.5})\) quantum query complexity, improving the best known algorithm of \(O(n^{1.5}\sqrt{\log n})\) [arXiv:quant-ph/0606127]. Applying this method to the maximum bipartite matching problem gives an \(O(n^{1.75})\) algorithm, improving the best known trivial \(O(n^2)\) upper bound.