A reachability query with attribute constraints checks whether there is a constraint satisfied path from source to destination in an attributed graph. When an answer 'No' is returned to the user, the user may wonder why there is no such path. The user may ask 'Am I setting the attribute constraint too restrictive?' or 'How can I reach the destination from the source?'. In this paper, we propose the How-to-Reach query for offering explanations to users in this situation. We first introduce a trick to minimally modify Dijkstra's algorithm, which is widely implemented in existing attributed graph database systems, for obtaining optimal How-to-Reach answers. Then, we propose a time and space efficient non-traversal based index for computing high-quality approximate answer and a hop reduction function that can harness the hop distance. Our experimental results show that our techniques can actually reduce computation time while offering high-quality answers with reasonable hop distances.