Graph Problem: Help find the distance between the two most widely separated nodes.

Question

I'm working through previous years ACM Programming Competition problems trying to get better at solving Graph problems.

The one I'm working on now is I'm given an arbitrary number of undirected graph nodes, their neighbors and the distances for the edges connecting the nodes. What I NEED is the distance between the two farthest nodes from eachother (the weight distance, not by # of nodes away).

Now, I do have Dijkstra's algorithm in the form of:

// Dijkstra's Single-Source Algorithm
private int cheapest(double[] distances, boolean[] visited)
{
        int best = -1;
        for (int i = 0; i < size(); i++)
        {
                if (!visited[i] && ((best < 0) || (distances[i] < distances[best])))
                {
                        best = i;
                }
        }
        return best;
}

// Dijkstra's Continued
public double[] distancesFrom(int source)
{
        double[] result = new double[size()];
        java.util.Arrays.fill(result, Double.POSITIVE_INFINITY);
        result[source] = 0; // zero distance from itself
        boolean[] visited = new boolean[size()];
        for (int i = 0; i < size(); i++)
        {
                int node = cheapest(result, visited);
                visited[node] = true;
                for (int j = 0; j < size(); j++)
                {
                        result[j] = Math.min(result[j], result[node] + getCost(node, j));
                }

        }
        return result;
}

With this implementation I can give it a particular node and it will give me a list of all the distances from that node. So, I could grab the largest distance in that list of distances but I can't be sure that any particular node is one of the two furthest ones at either end.

So the only solution I can think of is to run this Dijkstra's algorithm on every node, go through each returned list of distances and looking for the largest distance. After exhausting each node returning it's list of distances I should have the value of the largest distance between any two nodes (the "road" distance between the two most widely seperated villages). There has got to be an easier way to do this because this seems really computationally expensive. The problem says that there could be sample inputs with up to 500 nodes so I wouldn't want it to take prohibitively long. Is this how I should do it?

Here is a sample input for the problem:

Total Nodes: 5

Edges:
Nodes 2 - Connect - Node 4. Distance/Weight 25
Nodes 2 - Connect - Node 5. Distance/Weight 26
Nodes 3 - Connect - Node 4. Distance/Weight 16
Nodes 1 - Connect - Node 4. Distance/Weight 14

The answer to this sample input is "67 miles". Which is the length of the road between the two most widely separated villages.

So should I do it how I described or is there a much simpler and much less computationally expensive way?

Answer 1

You can use your Dijkstra's implementation as follows:

1. Pick a random node,(a), run Dijkstra from node a, and find the furthest node from it. Mark that node as node b.
2. Run Dijkstra again starting at node b, and find the furthest node from it. Mark that node as node c.

I don't have proof for this, but I think b and c will be furthest away nodes. You might need to run one more iteration (I'm still thinking about it).

Answer 2

So there's an implementation of Dijkstra which runs O(VlogV + E) giving your approach a complexity of roughly V^2logV + VE. See DADS. But perhaps more intuitive would be to run one of the all pairs shortest path algorithms like Floyd-Warshall or Johnsons. Unfortunately they're all roughly O(V^3) for dense graphs (close to the complete graph where E = V^2).

Answer 3

Multiply the edge weights by -1 and find the shortest path on the new graph. That would be the longest path on the original graph

Answer 4

If you want the longest shortest path that is

sup i,j {inf i,j {n : n=length of a path between i and j}}

you should certainly consider a all nodes shortest path algorithm like Flyod-Warshall as mentioned by others. This would be in the order of O(V^3).

If you want the longest possible path that is

sup i,j {n : n=length of a path between i and j}

you could try to use Midhat's idea. (which really is as complex as the original problem as pointed out in the comments) I would recommend to invert the weights with 1/w though, to retain positive weights, given the original weights were strict positive.

Another algorithm you might want to look up when dealing with negative weights is the algorithm of Bellman and Ford

Answer 5

Is this the Roads in the North problem?