Noah (angelbob) wrote,

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...

  • Welp, that's it.

    The last person I knew on here is moving over to DreamWidth. When I load my friends list (without her) I literally get one private post from me and…

  • Moved all my RSS feeds over...

    It looks like DreamWidth also supports creating unlimited RSS feeds for various stuff... I've moved all mine over. Okay, *now* my friends list looks…

  • Setting up DreamWidth...

    I now have This same userid already belongs to somebody else who has no posts and doesn't otherwise resemble me. Still…

  • Post a new comment


    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.