Noah (angelbob) wrote,
Noah
angelbob

Algorithms problem SOLVED

Okay, people saying I should check the algorithms book win this one :-)

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...
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 9 comments