gotchaModerate
Difference between diameter of a graph vs longest path of the graph
Viewed 0 times
paththegraphdifferencebetweendiameterlongest
Problem
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.
Solution
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,
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,
Context
StackExchange Computer Science Q#23284, answer score: 10
Revisions (0)
No revisions yet.