Re: Finding longest path between two vertices

In article <1182197872.234378.227740@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Googmeister <googmeister@xxxxxxxxx> wrote:
Right, Bellman-Ford works in directed graphs with no negative cycles.

Note that if the graph is acyclic, you can compute shortest/longest
path in linear time via topological sort.

Right.

On Jun 18, 3:36 pm, Jym <Jean-Yves.Moyen+n...@xxxxxxxxxxxx> wrote:
I agree that there is a problem for finding "longest simple path" (ie
without taking the same edge several times). The OP had not make it clear
if that's really what he meant by "longest path".

O.K., you could be right. However, usually "path" means that there are no
repeated vertices. "Hamiltonian path," "shortest path," etc., all mean no
repeated vertices in the literature. But, it's conceivable that the OP
meant to consider only acyclic directed graphs.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: An unusual sorting problem
    ... You just have to construct a graph as follows: ... This takes linear time to construct. ... Note that the labels do not need to be sorted, ... (this is the map that makes a graph node from a given label). ...
    (comp.programming)
  • Re: Two notions of linear time on a graph
    ... If we look at most linear time algorithms, the size of m does not need ... adjacency list structure in a graph and use it, ... the number of vertices (to set up an array of lists), ... There is another type of algorithm which might be said to run in ...
    (comp.theory)
  • Two notions of linear time on a graph
    ... I came across a subtle distinction between two notions of linear time ... If we look at most linear time algorithms, the size of m does not need ... adjacency list structure in a graph and use it, ... There is another type of algorithm which might be said to run in ...
    (comp.theory)
  • Re: topological sort of cyclic graph, how to break cycles, mapping ot other problems
    ... you're looking for some type of generalized topological sort. ... SCCs can be determined by a topological sort of the component graph. ... compute a minimal cut bipartition, i.e. look for a minimal cut ... bipartition heuristic available;-) So there might be better heuristics ...
    (comp.theory)
  • Re: detecting cycles in a directed graph
    ... Topological sort on a cyclic graph doesn't make much sense, ... "If this algorithm terminates without outputting all the nodes of the ...
    (comp.theory)