Problem Detail: I am curious what is the difference between diameter of a graph vs longest path of a graph. I just read diameter of a graph can be solved using Floyd warshall in O(V^3) while longest path can be calculated in O(V + E) using topological sort.
Asked By : user2615516
Answered By : babou
The longest path of the graph is the longest path between any two vertices. There may be several with the same longest length. Since you are comparing with the diameter, which is an integer, you probably mean the length of the longest path The diameter is the length of the longest of the shortest path between any two vertices. That means that you compute the shortest path for any pair of vertices, and take the longest one of them. The distance between two vertices being the shortest path, the diameter is the longest distance between two vertices,
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23284
