1. One or more computer-readable storage media containing instructions which, when executed by one or more processors disposed in an electronic device, perform a method for computing short paths in a scale-free directed graph, the method comprising the steps of: identifying one or more hubs in the graph, the hubs being high-degree vertices; pre-computing data structures for each of the one of more hubs, each of the pre-computed data structures comprising an in-tree and an out-tree, the in-tree including shortest paths directed from vertices in the graph to a given hub, the out-tree including shortest paths directed from the given hub to vertices in the graph, the pre-computing being performed prior to processing of a path query on the graph; and storing the pre-computed data structures.