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