During the last years, impressive progress has been achieved in the field of algorithm engineering. A problem becoming more and more important is that of data dependency: the performance of an algorithm often highly depends on the input. Yet, for a given input, it is highly non-trivial to select the best solving strategy. In this work, we introduce a new methodology for evaluating speed-up techniques for DijkstraŽs Algorithm: we examine the shortest-path structure of networks using simple indices in order to predict how well speed-up techniques perform on specific networks. More precisely, we introduce the ReCo-Index that indicates the strength of hierarchy of the input. In addition, we present a second index, called shortest-path entropy, taking into account the mutual importance of consecutive edges. As a third index, the update impact measures the change of the shortest-paths structure in a network whenever it is altered. For each index, we present an algorithm for computing it efficiently. An experimental evaluation confirms the correlation of indices and speed-up techniques.