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

Re: An algorithm

[luwenth.livejournal.com]

No, it doesn't...

Border cases:

• 1 node
  
• 2 nodes
  
• 3 nodes in a line.
  
• 3 nodes in a triangle.
  
• N nodes in a circle. (Shortest longest path should be floor of N/2)
  
• 4 nodes in a P shape (connections A-B-C with B-D and C-D).
  

• Start at a point on the graph, assign it a depth of 0.
  
• If there are no connecting nodes, yell current depth and node. Terminate. (1 node case.)
  
• Loop Start
  
  
  
  • Increment your depth.
    
  • For each connecting node:
    
    
    • If the node has no depth, assign the current depth to the node. Iterate.
      
    • If the node has a depth, and the depth is larger, assign the current depth to the node. Iterate. (You've just shortcut a loop.)
      
    • If the node has a depth, and the value is smaller, And the difference is > 1, assign the depth to the depth of the current node. Iterate. (You're not at an end, and there is a shorter way of getting here.)
      
    • If the node has a depth, and the value is the same as the current depth, terminate quietly. (This path has been traversed, so die quietly.)
      
    • If the node has a depth, and the value is smaller, And the difference is <= 1, yell the current depth and node. Terminate. (You've reached an end, and the depth is equal both ways of getting here.)
      

Of course, I just realized that I'm expecting that each of the explorers be able to yell a number and a node back at a central listener. As each explorer hits bottom, it will yell out a number and a node. If the central already has a depth for that node, and the new depth is smaller (which it invariably will be) then the new depth is recorded. Then once all the explorers have completed, the two nodes the listener knows about are the farthest apart, and the sum of their depths is the shortest longest path.

But short of that little issue, I think I've walked through all the potentials and it behaves appropriate, and terminates when it should (loudly or quietly).

No, I don't want to code it up :)

Re: An algorithm

[luwenth.livejournal.com]

Errr.. "the two nodes the listener knows about" should be "the two largest nodes the listener knows about" :)

Re: An algorithm

[luwenth.livejournal.com]

And nevermind again, my brilliance turned into bullshit *sigh*