Complex Networks-Finding all possible shortest paths between a pair of nodes

I have a database that describes a huge network. It consists of about 18000 vertices. Now I need to find all possible shortest paths between a pair of nodes. I have tried implementing the iterative DFS, but the problem there is the exponential growth.The amount of time needed gets huge, since there vertices having a high out-degree. Can you suggest of some algorithm that would work faster. The complex network that I have is directed and weighted.Any suggestions would be great help.

Thanks, Ekta

For a weighted graph with positive weights, one generally uses uniform-cost search, aka Dijkstra's algorithm. Other algorithms can be faster in specific cases. For example, if your data allow you to define a heuristic function, you could use A* instead. Or if your network is scale-free (i.e. its degree is power law distributed), you can use a variant of Dijkstra's algorithm described in Peng et al.'12.

There are also a bunch of related SO questions you might want to look at, such as Is there better way than a Dijkstra algorithm for finding fastest path that do not exceed specified cost or Are there faster algorithms than Dijkstra?.

EDIT: to find all shortest paths between a given pair of nodes, you can still use Dijkstra, with a few changes:

• Use a searching tree to apply the algorithm (by opposition to applying the algorithm based directly on the graph you explore). This way, you can easily represent several paths leading to the same node. See the WP Breadth-first search article to see an example of searching tree. So this is more a matter of data structure.
• Allow an already visited node to be visited again, provided 1) the path leading to this node is different from the one already represented in the tree, and 2) is not longer than this existing path. In terms of searching tree, this means allowing one graph-node to be represented as two distinct tree-nodes, each one in a different branch.
• Develop the tree until you find a first optimal solution, then go on developing the tree using the length of this solution as a limit (i.e. you stop developping a branch when it reaches this length).
• In the end, each branch containing the targeted node should correspond to an optimal shortest path.

You can also have a look at this question (although it concerns unweighted graphs): Finding all the shortest paths between two nodes in unweighted undirected graph