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
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.
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.
Sorry, did not get properly! Can you be please more elaborate!!
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.
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!
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.