Noah (angelbob) wrote,
Noah
angelbob

Algorithms Question

If you're not into programming, you're probably happier if you skip this.

Say you've got a graph. It's not a tree (i.e. it has cycles), and it's fully-connected (no subsets of it that aren't connected to the main graph). You've got the list of nodes and the list of connections.

You'd like to find the longest shortest path. That sounds silly, so lemme 'splain. For any two nodes there's a shortest path between them. If you were to look at every pair of nodes and find the shortest path, you'd like the longest of those.

So if you had a graph like this:

  A--o--o--o--o--o--o--o
           |           |
           o--o--o--o--o
                 |
           B--o--o


The longest shortest path would be between A and B, so length 9. The longest shortest path would *still* go the short way 'round the cycle (because it's a shortest path), so it would be 9 and not 13.

You're not guaranteed that there *are* any leaf nodes (remember, this isn't a tree, there are cycles), so a simple Minimum Spanning Tree won't help so much...

This stuff is for a nifty network connectivity problem that a friend is working on. I've written a little statistical simulator for these things, and I'm trying to find the longest shortest path in a 30,000-node graph in less than O(n^2) time...
Subscribe

  • 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 noahgibbs.dreamwidth.org. This same userid already belongs to somebody else who has no posts and doesn't otherwise resemble me. Still…

  • 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.
  • 20 comments

  • 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 noahgibbs.dreamwidth.org. This same userid already belongs to somebody else who has no posts and doesn't otherwise resemble me. Still…