Using dijkstra for top N paths

[Yuval]

We would like to present several path results using weighted path finding - instead of the "lightest" route, we'd like to present the 5 lightest routes.

Is that possible?

Has anyone done something similar?

Yuval

[Wes Freeman]

Please correct me if I'm misunderstanding your goal.

Is "lightest" a calculation of the sum of relationship costs? 

If so, check out:

http://stackoverflow.com/questions/12587263/cypher-order-by-path-cost/12588013#12588013

And:

http://console.neo4j.org/r/dygqp8

Note: reduce requires 1.9-SNAPSHOT.

Wes

Yuval

--
 
 

[Yuval Perlov]

Seems the idea is to traverse all possible paths... what if there are a lot of paths?  Dijkstra allows to find the best route but not the second third etc but all might be too complex. 

--
 
 

[Wes Freeman]

So, when you're saying lightest, are you talking about path lengths, or relationship properties with weights/scores on them?

Yeah, you can limit the result list of my query with LIMIT 5 (or something) to get the best 5, but if you have hundreds or thousands of paths it probably would get to be a slow query. 

Anyone know a better way to get the top n best paths? 

Wes

--
 
 

[Peter Neubauer]

Yves,

you could use some other algos such as A-start, see https://github.com/neo4j-examples/java-astar-routing for an example. Otherwise, via the Traversal Framewrok you have quite a lot of flexibility, see http://docs.neo4j.org/chunked/snapshot/tutorial-traversal.html

also, you can use the core Java API and utilities like Gremlin on top of it, see http://docs.neo4j.org/chunked/snapshot/gremlin-plugin.html#rest-api-flow-algorithms-with-gremlin fro an example of an algo built with that.

Enjoy!

/peter

--
 
 

--

Cheers,

/peter neubauer

G:  neubauer.peter
S:  peter.neubauer
P:  +46 704 106975
L:   http://www.linkedin.com/in/neubauer
T:   @peterneubauer

Wanna learn something new? Come to http://graphconnect.com

[Eugeny Kozhanov]

Can you add variable pathsCount to the Dijkstra algorithm and stop the solve when pathsCount = 5?

[Lasse Westh-Nielsen]

On Wed, Oct 3, 2012 at 12:20 AM, Yuval Perlov <yuval...@gmail.com> wrote:
> Seems the idea is to traverse all possible paths... what if there are a lot
> of paths? Dijkstra allows to find the best route but not the second third
> etc but all might be too complex.

Finding the shortest path involves looking at a lot of paths - think
about it, if you didn't, the shortest might be one of the ones you
didn't look at. It is the nature of the problem :)

Dijkstra in particular will find shortest paths to all reachable nodes
using some fixed starting point. Did you need multiple paths between
two fixed points instead? Then Dijkstra is not your friend.

- Lasse

[Yuval]

Do you have any idea who might be my friend?

The end result should be something similar to navigation apps where they show you several suggested routes.

[Lasse Westh-Nielsen]

On Wed, Oct 3, 2012 at 8:50 AM, Yuval <yuval...@gmail.com> wrote:
> Do you have any idea who might be my friend?
>
> The end result should be something similar to navigation apps where they
> show you several suggested routes.

I can't name any algorithms, but it will be some form of breadth-first
search that you terminate once you have enough paths. Maybe a modified
Dijkstra that doesn't optimise away longer paths?

Google is probably your friend, or maybe Peter or Craig who did Neo4j Spatial?

Regards,

Lasse

[Michael Hunger]

What about allShortestPaths?

Sent from mobile device

> --
>
>

[Mattias Persson]

Although the current Dijkstra algorithm could (easily) be modified to return the top N cheapest paths. The reason it stops is that there's an explicit check in there.

2012/10/3 Michael Hunger <michael...@neopersistence.com>

--

--
Mattias Persson, [mat...@neotechnology.com]
Hacker, Neo Technology
www.neotechnology.com

[Yuval]

allShortestPaths with subsequent path evaluation for some weights is the stop gap solution. As our data set grows we will manipulate the Dijkstra algorithm to return top n.

I am guessing algorithms are pluggable but failed to find somewhere that describes the process. Does anyone have a link?

BTW - is there a repository where we can showoff our Neo4j based creation?

Yuval

[Lasse Westh-Nielsen]

Yuval,

You cannot apply weights after the fact as you will only have one path per destination node to look at. The weights need to be considered as you go along. 

(You were looking for single pair shortest path right?)

Regards,

Lasse

--
 
 

[Yuval Perlov]

i agree it's a heuristic - i assume that if i correctly sort my top 10 shortest paths, the best path will actually be in there.

--