Opened 13 years ago
Closed 11 years ago
#181 closed enhancement (done)
Support multiple targets for Suurballe
Reported by: | Alpar Juttner | Owned by: | Peter Kovacs |
---|---|---|---|
Priority: | major | Milestone: | LEMON 1.2 release |
Component: | core | Version: | hg main |
Keywords: | Cc: | ||
Revision id: | 80ec623f529f |
Description (last modified by )
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).
Change History (11)
comment:1 Changed 13 years ago by
Owner: | changed from Alpar Juttner to Peter Kovacs |
---|
comment:2 Changed 13 years ago by
Summary: | Support multiple target for Suurball → Support multiple targets for Suurball |
---|
comment:3 Changed 12 years ago by
Description: | modified (diff) |
---|---|
Status: | new → assigned |
Summary: | Support multiple targets for Suurball → Support multiple targets for Suurballe |
comment:4 Changed 12 years ago by
Description: | modified (diff) |
---|
comment:5 Changed 12 years ago by
comment:6 Changed 12 years ago by
Currently there are findFlow()
and findPaths()
functions instead of start()
.
comment:7 Changed 12 years ago by
Priority: | minor → major |
---|
comment:8 follow-up: 9 Changed 12 years ago by
There are two problems that have to solved for this improvement:
- 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.) - The proposed interface conflicts with the current one: we already has an
init(s)
function, but it does not call Dijkstra. Nowinit(s); findFlow(t,k); findPaths();
is said to be equivalent torun(s,t,k)
, so it runs s-t Dijkstra k times (and no full Dijkstra).
comment:9 Changed 12 years ago by
Replying to kpeter:
- 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.
comment:10 Changed 12 years ago by
Milestone: | → LEMON 1.2 release |
---|
comment:11 Changed 11 years ago by
Resolution: | → done |
---|---|
Status: | assigned → closed |
[9a7e4e606f83] went to the main branch, this ticket can be closed.
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.