Turns out that for what I'm doing (called "multiple-source shortest path" in CLR) there's no faster way to do it than to run the single-source shortest path algorithm N times. Since all my edge weights are positive, I can use good old Dijkstra's algorithm, which is O(E * log V) if I use a priority queue. Since I have a sparse graph and my number of edges is a simple constant multiple of V (specifically, it's about 3 * V), that'll reduce my runtime to O( V log V ), which works nicely, and my space requirement to O(V). Unfortunately, O(V log V) for one pass still means O( V^2 log V ) for V passes, so the time requirement won't really be less.
I can get some additional speed in particular cases by switching from a priority queue to a Fibonacci Heap. Anybody remember Fibonacci Heaps? Yeah, I didn't think so. Mostly you're better off forgetting them.
Anyway, yeah, looks like I was wrong to think that I could solve this stuff faster than by just running the algorithm once for each vertex. I'm still trying to see if there's some extra optimization I can get because I just want the maximum path length... I suspect I can cut Dijkstra's algorithm off early in a lot of cases, which will help a little.
Now I just need to write a little priority queue implementation and code up Dijkstra...
