Longest path from u to v in a directed weighted graph
Hi, I would like to find the longest path from vertex u to vertex v through a directed graph with positive edge weights. I know that u and v are choke points in the graph, in that if you start from vertex u and start following random edges, you will end up at vertex v in pretty short order. Is dijkstra_shortest_paths the best function for this purpose? The vertices reachable from u without travelling through v form a small subgraph of the total graph. I want to avoid exploring beyond v, and I definitely don't need to know the distances to vertices beyond v. Cheers, Shaun
The graph is a DAG? If not, that is a NP-Complete problem and Dijkstra wouldn't help you. Regards, Murilo Adriano Vasconcelos http://murilo.wordpress.com Em 13/04/2011, às 21:11, Shaun Jackman <sjackman@bcgsc.ca> escreveu:
Hi,
I would like to find the longest path from vertex u to vertex v through a directed graph with positive edge weights. I know that u and v are choke points in the graph, in that if you start from vertex u and start following random edges, you will end up at vertex v in pretty short order. Is dijkstra_shortest_paths the best function for this purpose?
The vertices reachable from u without travelling through v form a small subgraph of the total graph. I want to avoid exploring beyond v, and I definitely don't need to know the distances to vertices beyond v.
Cheers, Shaun
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Murilo, The subgraph between u and v is a DAG — that is the subgraph reachable from u without travelling through v. The rest of the graph is not acyclic. Cheers, Shaun On Wed, 2011-04-13 at 17:21 -0700, Murilo Adriano Vasconcelos wrote:
The graph is a DAG? If not, that is a NP-Complete problem and Dijkstra wouldn't help you.
Regards,
Murilo Adriano Vasconcelos http://murilo.wordpress.com
Em 13/04/2011, às 21:11, Shaun Jackman <sjackman@bcgsc.ca> escreveu:
Hi,
I would like to find the longest path from vertex u to vertex v through a directed graph with positive edge weights. I know that u and v are choke points in the graph, in that if you start from vertex u and start following random edges, you will end up at vertex v in pretty short order. Is dijkstra_shortest_paths the best function for this purpose?
The vertices reachable from u without travelling through v form a small subgraph of the total graph. I want to avoid exploring beyond v, and I definitely don't need to know the distances to vertices beyond v.
Cheers, Shaun
On Thu, 14 Apr 2011, Shaun Jackman wrote:
Hi Murilo,
The subgraph between u and v is a DAG — that is the subgraph reachable from u without travelling through v. The rest of the graph is not acyclic.
In that case, there is a dag_shortest_paths algorithm that you can use (negating the edge weights). You might need to use filtered_graph (with a prior BFS) to isolate the part of the graph between u and v, or a visitor in the shortest path algorithm might work instead. -- Jeremiah Willcock
Cheers, Shaun
On Wed, 2011-04-13 at 17:21 -0700, Murilo Adriano Vasconcelos wrote:
The graph is a DAG? If not, that is a NP-Complete problem and Dijkstra wouldn't help you.
Regards,
Murilo Adriano Vasconcelos http://murilo.wordpress.com
Em 13/04/2011, às 21:11, Shaun Jackman <sjackman@bcgsc.ca> escreveu:
Hi,
I would like to find the longest path from vertex u to vertex v through a directed graph with positive edge weights. I know that u and v are choke points in the graph, in that if you start from vertex u and start following random edges, you will end up at vertex v in pretty short order. Is dijkstra_shortest_paths the best function for this purpose?
The vertices reachable from u without travelling through v form a small subgraph of the total graph. I want to avoid exploring beyond v, and I definitely don't need to know the distances to vertices beyond v.
Cheers, Shaun
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Thu, 2011-04-14 at 13:15 -0700, Jeremiah Willcock wrote:
On Thu, 14 Apr 2011, Shaun Jackman wrote:
Hi Murilo,
The subgraph between u and v is a DAG — that is the subgraph reachable from u without travelling through v. The rest of the graph is not acyclic.
In that case, there is a dag_shortest_paths algorithm that you can use (negating the edge weights). You might need to use filtered_graph (with a prior BFS) to isolate the part of the graph between u and v, or a visitor in the shortest path algorithm might work instead.
Hi Jeremiah, dag_shortest_paths looks promising. It starts by computing a topological ordering of the graph, and in fact I already have a topological ordering of the subgraph in which I'm interested. So, it looks as though I'll just use the algorithm that computes the longest path from the topological ordering. It would be nice if this algorithm were factored so that a user could provide a topological ordering as a parameter. Thanks, Shaun
On Wed, 2011-04-13 at 17:21 -0700, Murilo Adriano Vasconcelos wrote:
The graph is a DAG? If not, that is a NP-Complete problem and Dijkstra wouldn't help you.
Regards,
Murilo Adriano Vasconcelos http://murilo.wordpress.com
Em 13/04/2011, às 21:11, Shaun Jackman <sjackman@bcgsc.ca> escreveu:
Hi,
I would like to find the longest path from vertex u to vertex v through a directed graph with positive edge weights. I know that u and v are choke points in the graph, in that if you start from vertex u and start following random edges, you will end up at vertex v in pretty short order. Is dijkstra_shortest_paths the best function for this purpose?
The vertices reachable from u without travelling through v form a small subgraph of the total graph. I want to avoid exploring beyond v, and I definitely don't need to know the distances to vertices beyond v.
Cheers, Shaun
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi, 2011/4/14 Shaun Jackman <sjackman@bcgsc.ca>
On Thu, 2011-04-14 at 13:15 -0700, Jeremiah Willcock wrote:
On Thu, 14 Apr 2011, Shaun Jackman wrote:
Hi Murilo,
The subgraph between u and v is a DAG — that is the subgraph reachable from u without travelling through v. The rest of the graph is not acyclic.
In that case, there is a dag_shortest_paths algorithm that you can use (negating the edge weights). You might need to use filtered_graph (with a prior BFS) to isolate the part of the graph between u and v, or a visitor in the shortest path algorithm might work instead.
Hi Jeremiah,
dag_shortest_paths looks promising. It starts by computing a topological ordering of the graph, and in fact I already have a topological ordering of the subgraph in which I'm interested. So, it looks as though I'll just use the algorithm that computes the longest path from the topological ordering. It would be nice if this algorithm were factored so that a user could provide a topological ordering as a parameter.
Thanks, Shaun
The graph is a DAG? If not, that is a NP-Complete problem and Dijkstra wouldn't help you.
Regards,
Murilo Adriano Vasconcelos http://murilo.wordpress.com
Em 13/04/2011, às 21:11, Shaun Jackman <sjackman@bcgsc.ca> escreveu:
Hi,
I would like to find the longest path from vertex u to vertex v
On Wed, 2011-04-13 at 17:21 -0700, Murilo Adriano Vasconcelos wrote: through
a directed graph with positive edge weights. I know that u and v are choke points in the graph, in that if you start from vertex u and start following random edges, you will end up at vertex v in pretty short order. Is dijkstra_shortest_paths the best function for this purpose?
The vertices reachable from u without travelling through v form a small subgraph of the total graph. I want to avoid exploring beyond v, and I definitely don't need to know the distances to vertices beyond v.
Cheers, Shaun
If you already have a topological ordering of your subgraph, you only need to do one DFS to find the longest path. You can just do a DFS starting from the vertex with in-degree 0 (the root of topological tree) (if your subgraph is not connected, you'll need to do a DFS from each vertex with in-degree 0) and save the maximum depth you find. Regards, -- Murilo Adriano Vasconcelos http://murilo.wordpress.com
On 4/13/11 8:11 PM, Shaun Jackman wrote:
Hi,
I would like to find the longest path from vertex u to vertex v through a directed graph with positive edge weights. I know that u and v are choke points in the graph, in that if you start from vertex u and start following random edges, you will end up at vertex v in pretty short order. Is dijkstra_shortest_paths the best function for this purpose?
The vertices reachable from u without travelling through v form a small subgraph of the total graph. I want to avoid exploring beyond v, and I definitely don't need to know the distances to vertices beyond v.
Cheers, Shaun
Thinking about this a bit, to find the LONGEST length will by necessity require every path, because there is no way to trim a set of paths and say they can't be longer then the current longest. Shortest finding algorithms can trim the search space since once you get from u to a in distance d, once your current path is bigger than d you don't need to check going through a anymore. Since you say it forms a small DAG, a quick depth first search, keeping track of the longest path may be best. -- Richard Damon
participants (4)
-
Jeremiah Willcock -
Murilo Adriano Vasconcelos -
Richard Damon -
Shaun Jackman