Algorithms Question

[noahgibbs]

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

Comments

[angelbob.livejournal.com]

Your longest shortest path is also going to cross at least one cut edge.

Hm. I don't think I'm familiar with minimum cuts. Remind me what that is? I tried a lot of variations involving minimum spanning trees, if that's similar.

Even if you just do the simple O(|V|^2) algorithm, I'll bet you can improve it by memoizing (bet you haven't heard that word since you were at CMU) all the intermediate results.

You can, but I'd *really* like to avoid memoizing on an O(N^2)-in-space algorithm for 30,000 nodes if it's at all possible...

Also, it's not clear what you'd memoize. Shortest paths between various nodes, I suppose, so you could basically add virtual edges to the graph (marked with edge lengths which are the shortest path) until it's fully connected. Which is what the memoizing would wind up doing.

Hm. That'd still be a lot faster than several of the things I was contemplating, though.

Minimum cut

[bredmold.livejournal.com]

A minimum cut is minimal set of edges (either the least cardinality or the least total weight in a weighted graph) that must be removed from a connected graph to render it disconnected (at least two separate components). A minimum cut is not necessarily unique, but neither is a longest shortest path.

Re: Minimum cut

[angelbob.livejournal.com]

Hm. Okay, I could see that. Seems like you'd need to calculate a lot of them and try them all, though... Since, y'know, the longest shortest path could be entirely outside the bit you just disconnected from the main bulk of the graph.