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(\sqrtB(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łog 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.