[pgrouting-users] algo which allow negative cost

[Yaron Lev]

Hi,

i am wondering if there is any algo within pgrouting 2, which will allow
edges to have negative costs (without negative circles)?

i was not able to find such, and in this event, is there some clever way,
to achieve a similar effect?

in specific, i am trying to solve a pac-man like problem.

trying to find best route, given graph, where on some edges there are
"fruits" to collect, collecting fruits will have a positive effect.

your goal to collect as many fruits as possible, fruit can have a -1 cost
for example while each edge has it length as a positive cost.

the outcome should be a route, where at any distance(this is flexible, as
long as it achieve a similar goal) from route, the outcome route will have
the best score out of all other routes.

i tried using shortest path algo, with out negative costs, but i am unable
to come up with a solution which will indeed provide such or similar
solution. (in specfic un able to come up with costs, which will indeed
"force" the route to collect those "fruits")

i will appreciate any insight or direction for solving this problem.


* the fruits are actually poi, such as bus stations, museums etc.
* if negative edge costs are allowed, the problem is solved.

thanks for your help!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20130708/829dc02e/attachment.html>