You can't pre-compute it with the Floyd-Warshall algorithm in C or something?

EDIT: to try to answer my own calculation on the back of the envelope...

We're going to need n^2 space and n^3 time, where n is the number of nodes. There are about 3.5 million articles (http://en.wikipedia.org/wiki/Wikipedia:Size_of_Wikipedia), and if we assume that the diameter of the Wikipedia graph is 255 or less, we need 1 byte * 3.5 million * 3.5 million = 12.25 TB just to store path lengths for all pairs. It's also going to take a while because locality is going to be hosed. You might be able to do something smarter, like do the all-pairs solutions for something that will fit in memory (top 30000 pages or so), and hope that queries match a long-tail distribution...