# Longest Path between two vertices

I have a directed graph with weighted edges (weights are all positive).

Now, I'm looking for an efficient algorithm or code (specifically, C#) to find the longest path between two given vertices.

-
Have you made an attempt? If so, could you edit to include your idea? –  statenjason Aug 10 '09 at 18:08
Is this a homework problem? –  David Berger Aug 10 '09 at 18:13
@David, Yeah, sounds like a project for an Algorithms course. –  Steve Aug 10 '09 at 18:30

This is exactly equivalent to a shortest-path algorithm with all negative weights. To do that, you need to verify that there are no negative-weight cycles (which in your original case is probably equivalent to verifying no positive-weight cycles). Best bet is to take the additive inverse of the weights and run Bellman-Ford, then take the additive inverse of the result.

-

David Berger's answer is correct, unless you mean a simple path, where each vertex can occur at most once, in which case Bellman-Ford will not give the longest path. Since you say the weights are positive, it's not possible for a longest path to exist when the graph has a cycle (reachable from the source), unless you mean simple path. The longest simple path problem is NP-complete. See Wikipedia.

So, let's assume you mean a directed acyclic graph (DAG). In linear time, you can compute the longest path to each vertex v from the start vertex s, given that you know the longest path from s->*u for each u where u->v directly. This is easy - you can do a depth first search on your directed graph and compute the longest path for the vertices in reverse order of visiting them. You can also detect back edges whole you DFS using a 3-color marking (opened but not finished vertices are gray). See Wikipedia again for more information. Longest/shortest path finding on a DAG is sometimes called the Viterbi algorithm (even though it was given assuming a specific type of DAG).

I'd attempt the linear time dynamic programming solution first. If you do have cycles, then Bellman-Ford won't solve your problem anyway.

-
A longest path can exist with cycles if they are not reachable. Moreover, Bellman-Ford can be made to return negative infinity if any negative-weight cycles are reachable. So this is still a reasonable question to ask even without explicitly assuming that the graph is acyclic. Perhaps this is why the first wikipedia article you link recommends Bellman-Ford. –  David Berger Aug 10 '09 at 20:26
Sure, while you're preparing your topological order, DFS to detect whether the subgraph reachable from the source has a cycle. –  Jonathan Graehl Aug 11 '09 at 7:37
The only reason to use bellman-ford for longest path is 1) there are reachable cycles 2) but all those cycles are 0 or negative weight (before weight inversion) –  Jonathan Graehl Aug 11 '09 at 8:01
The text passage discusses the problem of finding the longest path between two vertices in a directed graph with positive edge weights. It mentions various algorithms and conditions under which they can be applied, such as the Bellman-Ford algorithm and the Viterbi algorithm for directed acyclic graphs (DAGs).
no_question

the passage does not contain a direct mathematical question or a request for a specific calculation. instead, it provides a discussion and suggestions for solving a problem in graph theory.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Longest Path between two vertices

I have a directed graph with weighted edges (weights are all positive).

Now, I'm looking for an efficient algorithm or code (specifically, C#) to find the longest path between two given vertices.

-
Have you made an attempt? If so, could you edit to include your idea? –  statenjason Aug 10 '09 at 18:08
Is this a homework problem? –  David Berger Aug 10 '09 at 18:13
@David, Yeah, sounds like a project for an Algorithms course. –  Steve Aug 10 '09 at 18:30

This is exactly equivalent to a shortest-path algorithm with all negative weights. To do that, you need to verify that there are no negative-weight cycles (which in your original case is probably equivalent to verifying no positive-weight cycles). Best bet is to take the additive inverse of the weights and run Bellman-Ford, then take the additive inverse of the result.

-

David Berger's answer is correct, unless you mean a simple path, where each vertex can occur at most once, in which case Bellman-Ford will not give the longest path. Since you say the weights are positive, it's not possible for a longest path to exist when the graph has a cycle (reachable from the source), unless you mean simple path. The longest simple path problem is NP-complete. See Wikipedia.

So, let's assume you mean a directed acyclic graph (DAG). In linear time, you can compute the longest path to each vertex v from the start vertex s, given that you know the longest path from s->*u for each u where u->v directly. This is easy - you can do a depth first search on your directed graph and compute the longest path for the vertices in reverse order of visiting them. You can also detect back edges whole you DFS using a 3-color marking (opened but not finished vertices are gray). See Wikipedia again for more information. Longest/shortest path finding on a DAG is sometimes called the Viterbi algorithm (even though it was given assuming a specific type of DAG).

I'd attempt the linear time dynamic programming solution first. If you do have cycles, then Bellman-Ford won't solve your problem anyway.

-
A longest path can exist with cycles if they are not reachable. Moreover, Bellman-Ford can be made to return negative infinity if any negative-weight cycles are reachable. So this is still a reasonable question to ask even without explicitly assuming that the graph is acyclic. Perhaps this is why the first wikipedia article you link recommends Bellman-Ford. –  David Berger Aug 10 '09 at 20:26
Sure, while you're preparing your topological order, DFS to detect whether the subgraph reachable from the source has a cycle. –  Jonathan Graehl Aug 11 '09 at 7:37
The only reason to use bellman-ford for longest path is 1) there are reachable cycles 2) but all those cycles are 0 or negative weight (before weight inversion) –  Jonathan Graehl Aug 11 '09 at 8:01
user
The text passage discusses the problem of finding the longest path between two vertices in a directed graph with positive edge weights. It mentions various algorithms and conditions under which they can be applied, such as the Bellman-Ford algorithm and the Viterbi algorithm for directed acyclic graphs (DAGs).

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question or a request for a specific calculation. Instead, it provides a discussion and suggestions for solving a problem in graph theory.