Dijkstra SPP can take multiple start vertices.

[mfuchs]

Instead of a single start vertex a range of start vertices can be handed in. The range is modeled by two iterators s_begin and s_end.

The reason to use iterators is to be consistent with dijkstra_shortest_path that already supports multiple start vertices for some functions. Moreover, another advantage of iterators is backwards compatibility with the existing functions since the parameter count is different.

[e-kwsm]

Just for information. Boost already has floyd_warshall_all_pairs_shortest_paths, which finds the shortest paths between ALL pairs of vertices and has complexity of O(V^3); current dijkstra_shortest_paths has complexity of O(V log V + E).

[mfuchs]

Thanks for the information and the reply Floyd-Warshall fits a different use case than mine.

I am interested in the shortest path of any of [s_start, s_end) to some end points. I am not interested what the shortest paths of s_1, s_2, ..., s_m to x_1, x_2, ..., x_n are. Instead I am interested in min(spp(s_1, x_i), spp(s_2, x_i), ..., spp(s_n, x_i)) for all i in 1 to n. My adaptions to Dijkstra SPP do that in O(V log V + E).

In work I could use these changes. At the moment I have to call dijkstra_shortest_paths multiple times and "merge" the results. So my code is more complex and slower than needed.

[Belcourt]

While this seems to build and run okay, I'm a bit reluctant to break the existing dijkstra_shortest_paths API. Can you refactor this to add a new overloaded method that takes the iterator pair, and leave the single vertex descriptor implemenation unmodified? Perhaps you considered this already, in which case could you explain why breaking the existing API is preferable to adding a new overloaded dijkstra_shortest_paths?

[mfuchs]

Thanks for your reply. I tried to make sure not to break the public API by having function pairs: One taking a single vertex, the other taking iterators. To avoid code duplication the single vertex versions internally forward to their iterator counterparts. Maybe I have overlooked something, could you please tell me in which case I broke the API?

[anadon]

I'm helping out with the PR backlog. Looks like you have a feature addition, test, but no new examples or documentation. I would like you to add documentation and examples. This is to let you know and help me prioritize PR's.

[jeremy-murphy]

@mfuchs you need to rebase your branch.

[anadon]

I tried rebasing locally and it needs more work than I can put in in the midst of coursework.

[anadon]

@jzmaddock The original author has been MIA for a while. Should this be closed?

[jzmaddock]

@jeremy-murphy, @Belcourt, any thoughts on this one?

[mfuchs]

I might have time the following weeks to look at this.

[jeremy-murphy]

@jeremy-murphy, @Belcourt, any thoughts on this one?

I think this is a neat extension to the classic single-source definition of Dijkstra's algorithm.

There is nothing wrong with the programming API as Belcourt believed.

Because it breaks the intuitive and documented single-source definition of Dijkstra's algorithm, it needs explanation and examples in the documentation.

If there is a published paper on this extension to single-source Dijkstra's algorithm then that would be a useful link to provide too.

[jeremy-murphy]

• [ ] documentation
• [ ] examples

Sorry, just experimenting with this Task List feature. But also I think this feature is worth pursuing. :)

[mfuchs]

@jeremy-murphy sorry it took me ages to update it, but now I finally got around it. I have also provided documentation and examples.