java - How to find the distance between the two most widely separated nodes -

i'm working through previous years acm programming competition problems trying better @ solving graph problems.

the 1 i'm working on i'm given arbitrary number of undirected graph nodes, neighbors , distances edges connecting nodes. need distance between 2 farthest nodes eachother (the weight distance, not # of nodes away).

now, have dijkstra's algorithm in form of:

// dijkstra's single-source algorithm private int cheapest(double[] distances, boolean[] visited) {         int best = -1;         (int = 0; < 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; // 0 distance         boolean[] visited = new boolean[size()];         (int = 0; < size(); i++)         {                 int node = cheapest(result, visited);                 visited[node] = true;                 (int j = 0; j < size(); j++)                 {                         result[j] = math.min(result[j], result[node] + getcost(node, j));                 }          }         return result; } 

with implementation can give particular node , give me list of distances node. so, grab largest distance in list of distances can't sure particular node 1 of 2 furthest ones @ either end.

so solution can think of run dijkstra's algorithm on every node, go through each returned list of distances , looking largest distance. after exhausting each node returning it's list of distances should have value of largest distance between 2 nodes (the "road" distance between 2 seperated villages). there has got easier way because seems computationally expensive. problem says there sample inputs 500 nodes wouldn't want take prohibitively long. how should it?

here sample input 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 sample input "67 miles". length of road between 2 separated villages.

so should how described or there simpler , less computationally expensive way?

it looks can use either of:

• floyd warshall algorithm
• johnson's algorithm.

i can't give guidance them though - i'm no expert.