COIN-OR::LEMON - Graph Library

Opened 16 years ago

Last modified 15 years ago

#181 closed enhancement

Support multiple targets for Suurballe — at Version 4

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 Peter Kovacs)

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 (4)

comment:1 Changed 16 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Peter Kovacs

comment:2 Changed 16 years ago by Alpar Juttner

Summary: Support multiple target for SuurballSupport multiple targets for Suurball

comment:3 Changed 16 years ago by Peter Kovacs

Description: modified (diff)
Status: newassigned
Summary: Support multiple targets for SuurballSupport multiple targets for Suurballe

comment:4 Changed 16 years ago by Peter Kovacs

Description: modified (diff)
Note: See TracTickets for help on using tickets.