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

[luwenth.livejournal.com]

What's the maximum number of connections that a node can have? I think this is important for some reason...

[bredmold.livejournal.com]

I should know this. I'll post a few random thoughts, but all the relevant reference volumes are at my office right now.

Your longest shortest path is also going to cross at least one cut edge. So, you should be able to get a lot of information out of calculating the minimum cut... which is doable in O(|V|+|E|) time if I recall (if I'm wrong, then it's O(|V|*|E|), which is a much bigger number).

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.

If all else fails, I'll try and remember to follow up on this tomorrow when I have some reference books in front of me.

[r-transpose-p.livejournal.com]

Also, do you need the *exact* longest shortest path?

some links

[treys.livejournal.com]

The straightforward approaches. (http://www.cs.rochester.edu/u/leblanc/csc173/graphs/apsp.html)

A fast heuristic approach. (http://www.dl.ac.uk/TCSC/Staff/Hu_Y_F/PROJECT/pdcp_siam/node8.html)

A very thorough tech report on the subject. (http://citeseer.nj.nec.com/pettie02faster.html)