That was actually the original idea but the CPU behind it (requires a lot of ram and multiple systems the way I worked it) was too expensive to swing by the wife for a goof off project ;)
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...