5
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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,

$\endgroup$
  • 1
    $\begingroup$ Well, this was a word confusion started by the fact that the question mixed a distance with a path to begin with. But you are right. $\endgroup$ – babou Mar 31 '14 at 6:24
  • $\begingroup$ It might be useful to include a small example where the two notions don't coincide. $\endgroup$ – Raphael Mar 31 '14 at 8:23
  • 1
    $\begingroup$ I know you know this, but it is not necessary to compute the shortest path distance for every pair of vertices to find out what the diameter is. It is, of course, the obvious way of doing it. $\endgroup$ – Juho Mar 31 '14 at 9:26
  • $\begingroup$ @Raphael: A triangle works. In general, $K_n$ has diameter 1 and paths of length $n-1$. $\endgroup$ – Louis Mar 31 '14 at 11:31
  • $\begingroup$ @Juho Yes. But I believe definitions should always be as simple as possible, the rest being a matter for theorems. But when two properties are equivalent, it is a matter of taste which should be the defining one. $\endgroup$ – babou Mar 31 '14 at 11:36
5
$\begingroup$

In general, they are not the same thing. Also, for the general graph, it is easy to compute the diameter, but hard to compute the longest path. In the graph below, the diameter is 4. A path from $6$ to $2$ is highlighted, which is of length 4.

enter image description here

However, there is a longer (simple) path from $6$ to $2$ of length 5.

enter image description here

$\endgroup$
  • $\begingroup$ And there's an even longer path of length 7, though not between those two vertices. $\endgroup$ – David Richerby Mar 31 '14 at 9:47
  • $\begingroup$ @DavidRicherby Yeah, you'll find one between say 7 and 3. $\endgroup$ – Juho Mar 31 '14 at 9:51
  • $\begingroup$ "hard" meaning NP-hard here. $\endgroup$ – Raphael Mar 31 '14 at 11:37
3
$\begingroup$

Topological sort is only defined for directed acyclic graphs so you can't use it to find longest paths in general directed graphs or undirected graphs. Finding the longest path in an undirected graph (in the whole graph or between two specific vertices) is NP-hard. I assume this holds for cyclic directed graphs, too.

Note that it's "unfair" to compare Floyd Warshall with an algorithm for finding the longest single path in a graph. Floyd Warshall computes $\Theta(n^2)$ different things (the length of the shortest path between every pair of vertices) so it's running time is, in a sense, $O(n)$ per answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.