Support multiple targets for Suurballe

[Alpar Juttner]

The concept is that

run(s,t,k);

would do just as it does now, but in addition to it, there would be a function

init(s);

performing a full Dijkstra and computing reduced arc costs, which could be then followed by several

start(t,k);

execution, each of them would reverse the arcs on the shortest s-t path found by init(s) and execute partial Dijkstra to t only k-1 times.

It could speed up the use cases when k arc-disjoint s-t paths are needed for a lot of t nodes (e.g. all t!=s nodes).

[Peter Kovacs]

Note that the current implementation is a specialization of the Successive Shortest Path algorithm for the Minimum Cost Flow problem.

In fact, Suurballe and Suurballe-Tarjan algorithms only solves this problem for the case of k=2, however with a much better theoretical time complexity (due to a more sophisticated method). It would be nice to implement these algorithms and compare the efficiency to the current implementation for k=2.

[Peter Kovacs]

Currently there are findFlow() and findPaths() functions instead of start().

[Peter Kovacs]

There are two problems that have to solved for this improvement:

1. The potentials (node distances) have to be "saved" after the first full Dijkstra, and they have to be reverted to this state at the beginning of each start() call. (And the flow have to be set to zero on all arcs.)
2. The proposed interface conflicts with the current one: we already has an init(s) function, but it does not call Dijkstra. Now

     init(s);
     findFlow(t,k);
     findPaths();
   

   is said to be equivalent to run(s,t,k), so it runs s-t Dijkstra k times (and no full Dijkstra).

[Peter Kovacs]

Replying to kpeter:

2. The proposed interface conflicts with the current one: we already has an init(s) function...

A possible solution is to use different names. In #323, [9a7e4e606f83] is proposed with an implementation.

[Peter Kovacs]

[9a7e4e606f83] went to the main branch, this ticket can be closed.