On extremely large data sets like that, to get such fast results, I find it best to use a union-find data structure with path compression. However, if you are looking to only use Djikstra's algorithm and optimize that, it comes down to what information each node in the graph has. You most likely do not need to do all 1,500 queries.
For instance, consider the following example. Lets say I am trying to find the degrees of separation between any 2 actors (the Bacon number) and I want to find the least weighted path(path using the newest movies possible). Now, let's say I have a function called shortestPath(actor A, actor B);
. Consider the following scenario.
If Actor A has been acting since 1970 and Actor B has been acting since 2000, then given that info, it would be much more logical to find a path starting from the first movie of Actor B and then traversing your way to Actor A. As opposed to iterating through every movie Actor A has acted in.
Thus, the main point is that the optimization of Djikstra's algorithm really depends on what your data set is. You would need to provide more information on what your data set entails for us to help you optimize your algorithm.
EDIT: Let's say you are trying to find the shortest path between 2 cities in the same country and if this country is longer than it is wider, for instance, Argentina, then you can do your queries based on the longitude and latitude of the countries boundaries. Then you can start to traverse vertically(using longitude) as opposed to horizontally. Ofc, there would need to be exception handling, but you get the general idea.