Suppose I have a adjacency matrix of a simple graph. Can anyone provide me some idea/algorithm to find the longest distance between any 2 vertices? I need it to find eccentricity of each vertex of a graph.

Printable View

- 04-24-2008anirbanLongest Distance - Graph Theory
Suppose I have a adjacency matrix of a simple graph. Can anyone provide me some idea/algorithm to find the longest distance between any 2 vertices? I need it to find eccentricity of each vertex of a graph.

- 04-24-2008tabstop
You don't want to find the longest distance between any two vertices, which doesn't exist anyway (imagine a triangular cycle; I can get from A to C in as many steps as I want, by just going back and forth from A to B until I get tired, and then going to C).

What you want to find is the first n such that every other node is reachable in at most n steps. The standard interpretation of (A)^n will come in handy here. - 04-25-2008anirban
Sorry, did not get properly! Can you be please more elaborate!!

- 04-25-2008CornedBee
He's saying that your formulation of the problem is misleading.

What you're looking for is the longest minimal path of the graph. I believe using an all_pairs_shortest_path algorithm followed by selecting the maximum of the results should yield a solution. I don't know if that's the most efficient way of doing it. - 04-25-2008anirban
Oh I see!!! Are you sure that it would work? I am not saying about your knowledge. I am saying it because I have it implement in the project!! So making it sure!

- 04-25-2008PING
What you can do is run a bfs to completion and choose the last instance of visit to your destination node. Alternatively, if you have weighed edges, you can use Dijkstra's algorithm. You might want to first run a cycle finding algorithm to find cycles in your graph. In case of cycles on the intended path, you would have a path of infinite length from your start node to the end node.