[BGL] dijkstra_shortest_paths and the single-pair problem
I would like to use the dijkstra_shortest_paths algorithm to find the shortest path from one specified vertex to another. The standard Boost implementation will find this, but it will continue until it has found the shortest paths to all nodes in the graph (i.e. solved the single source problem). The BGL book (Section 5.1, pp76) says: "It turns out that there are no algorithms for solving the single-pair problem that are asymptotically faster than the algorithms that solve the single-source problem". I think this is because the single-source algorithms all have the property that it is possible to determine whether the shortest path to any given node has been found during the execution of the algorithm, therefore you can use the same algorithm to solve both types of problem provided that the termination criterion is appropriate to the problem. Consider this problem: "find the shortest path from a source vertex u to a nearby destination vertex v in an infinitely large directed weighted graph G in finite time." The single-source problem can only be solved in infinite time, but the single-pair problem can be solved relatively quickly (because the two vertices are near each other). I think that the termination criterion is quite straightforward using a DijkstraVisitor - it is when vis.finish_vertex(u, g) is called and u == destination_node. Unfortunately I can't see how to stop the algorithm in a reasonable way. An unreasonable solution is to provide a custom graph and turn off all its edges when the termination criterion is met. This is unreasonable because the responsibility for termination belongs to the algorithm, not the data structure - I shouldn't have to modify the data structure to terminate the algorithm. It's also unreasonable because I have to customise both the graph and the algorithm to do something very simple. Is there a better way? Thanks Richard
Richard Jepps wrote:
I would like to use the dijkstra_shortest_paths algorithm to find the shortest path from one specified vertex to another.
The standard Boost implementation will find this, but it will continue until it has found the shortest paths to all nodes in the graph (i.e. solved the single source problem).
The BGL book (Section 5.1, pp76) says: "It turns out that there are no algorithms for solving the single-pair problem that are asymptotically faster than the algorithms that solve the single-source problem". I think this is because the single-source algorithms all have the property that it is possible to determine whether the shortest path to any given node has been found during the execution of the algorithm, therefore you can use the same algorithm to solve both types of problem provided that the termination criterion is appropriate to the problem.
Consider this problem: "find the shortest path from a source vertex u to a nearby destination vertex v in an infinitely large directed weighted graph G in finite time." The single-source problem can only be solved in infinite time, but the single-pair problem can be solved relatively quickly (because the two vertices are near each other).
I think you're reasoning is correct, but I've did not though a lot about it. The difference here is between worst-case complexity, which is the same O(V+E) for both problems, and average/minimum complexity.
I think that the termination criterion is quite straightforward using a DijkstraVisitor - it is when vis.finish_vertex(u, g) is called and u == destination_node. Unfortunately I can't see how to stop the algorithm in a reasonable way.
I happen to need something similiar --- prevent depth_first_visit from traversing out-edges of certain vertices. I've implemented this using functional object which is called when vertex is discovered and tells if the vertex is terminating or not. Something very similiar is possible for breadth_first_search, which is used internally by Dijkstra. The remaining problems are: - decide how to change dijstra_shortest_path interface. Guess it better accept a single target vertex and create appropriate terminating functor internally. - implement this. I can help with it, but unfortunately, have no time at the moment to implement it myself. I can provide you with the modified depth_first_search.hpp, if you'd like to see more details. - Volodya
Volodya,
The difference here is between worst-case complexity, which is the same O(V+E) for both problems, and average/minimum complexity.
That's right - the worst case is that the target vertex is the last one to be analysed because it is the furthest from the source vertex. If the target vertex is quite near to the source vertex stopping early represents a significant optimisation. In my application a high proportion of the shortest path problems are like this.
- decide how to change dijstra_shortest_path interface. Guess it better accept a single target vertex and create appropriate terminating functor internally.
This would be the easiest to understand from an API point of view, but it does involve either adding a new function or changing the API of the existing function. If there was a function call that told the algorithm to stop it would be very easy to implement a visitor without changing the API at all. It might also be possible to add the target vertex as a property to extend the API in a way that is compatible with current single-source clients.
- implement this.
I'm probably not the best person to do this because my C++ is not that good, and I would have to get my employer to agree not to claim the copyright. I'll see what I can do.
I can help with it, but unfortunately, have no time at the moment to implement it myself. I can provide you with the modified depth_first_search.hpp, if you'd like to see more details.
This would be very helpful. Is it OK for you to post it here? If not, my e-mail address is richard-dot-jepps-at-bentley-dot-com (sorry about the spam precautions). Thanks for your help. Richard
"Richard Jepps" <yg-boost-users@m.gmane.org> writes:
I think that the termination criterion is quite straightforward using a DijkstraVisitor - it is when vis.finish_vertex(u, g) is called and u == destination_node. Unfortunately I can't see how to stop the algorithm in a reasonable way.
An unreasonable solution is to provide a custom graph and turn off all its edges when the termination criterion is met. This is unreasonable because the responsibility for termination belongs to the algorithm, not the data structure - I shouldn't have to modify the data structure to terminate the algorithm. It's also unreasonable because I have to customise both the graph and the algorithm to do something very simple.
Is there a better way?
The best (and most efficient) way to terminate graph algorithms early is by throwing an exception. That's the intended way to use the library, and it is documented that way in the FAQ. The alternative would be to have every visitor explicitly checking for termination at every step, which would impose a high efficiency burden for large problems. HTH, -- Dave Abrahams Boost Consulting www.boost-consulting.com
David,
The best (and most efficient) way to terminate graph algorithms early is by throwing an exception. That's the intended way to use the library, and it is documented that way in the FAQ.
Thanks for pointing this out - for future readers the link is: http://www.boost.org/libs/graph/doc/faq.html It is also worth noting that http://www.boost.org/libs/graph/doc/table_of_contents.html links to a lot of information that isn't in the BGL book.
The alternative would be to have every visitor explicitly checking for termination at every step, which would impose a high efficiency burden for large problems.
The algorithm already checks for termination for each node it deals with (if Q is empty in BFS), so the performance penalty would be very small. It might even be possible to define the test at compile time so that there was no performance penalty unless you explicitly ask for the check. The main problem with using an exception is that the solution to the single-source problem is a single function call, the solution to the single-pair problem is to implement a visitor using an exception - which would not be obvious to many Boost users (the developers are in a different league). It's as if the function has been made deliberately hard to use for half its potential users. Thanks for your reply, and sorry for asking a question that's been asked before. I did look, but I didn't find. Richard
"Richard Jepps" <yg-boost-users@m.gmane.org> writes:
David,
The best (and most efficient) way to terminate graph algorithms early is by throwing an exception. That's the intended way to use the library, and it is documented that way in the FAQ.
Thanks for pointing this out - for future readers the link is: http://www.boost.org/libs/graph/doc/faq.html
It is also worth noting that http://www.boost.org/libs/graph/doc/table_of_contents.html links to a lot of information that isn't in the BGL book.
The alternative would be to have every visitor explicitly checking for termination at every step, which would impose a high efficiency burden for large problems.
The algorithm already checks for termination for each node it deals with (if Q is empty in BFS), so the performance penalty would be very small.
I don't buy that conclusion. The visitor has many points-of-customization, each of which might signal termination. Checking at each of those points could get expensive. If you want to terminate early by force-clearing the queue, I guess that won't impose any overhead, but any check that requires *additional* cycles on each step of the algorithm can add up.
It might even be possible to define the test at compile time so that there was no performance penalty unless you explicitly ask for the check.
That's certainly possible, providing your compiler cooperates. But most optimizers can also eliminate a call to an inline function which always returns the same boolean value and a branch which depends on that result -- so it's more than likely to be wasted optimization. I'm more concerned about the cost to performance of doing the additional termination check on each step of the algorithm.
The main problem with using an exception is that the solution to the single-source problem is a single function call, the solution to the single-pair problem is to implement a visitor using an exception - which would not be obvious to many Boost users (the developers are in a different league). It's as if the function has been made deliberately hard to use for half its potential users.
I understand the problem with comprehensibility. Furthermore, AFAIK nobody has every really measured the speed difference in the two approaches, so it may be OK to do it the "straightforward" way. I'd just like to see some numbers before anyone starts changing the BGL interfaces.
Thanks for your reply, and sorry for asking a question that's been asked before. I did look, but I didn't find.
Not a problem. -- Dave Abrahams Boost Consulting www.boost-consulting.com
participants (3)
-
David Abrahams -
Richard Jepps -
Vladimir Prus