Dijkstra's algorithm for shortest path
351 views
Skip to first unread message
Ariel deGraaf
Mar 21, 2021, 6:32:26 AM3/21/21
to gremli...@googlegroups.com
Hello,
g.V("687").repeat(outE().inV().simplePath()).until(hasId("1343")).
path().as('p').
map(unfold().coalesce(values('dist'),
constant(0.0)).sum()).as('cost').
order().by(select('cost')).
I am looking for an efficient way to calculate the shortest route between two vertices on a graph existing of approx. 5000 vertices and 15000 edges, taking into account the sum of the edge lengths (property 'dist' on each edge).
A well-known algorithm for this problem is Dijkstra's algorithm (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). This algorithm picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Has such an algorithm ever been implemented in Gremlin, or is it something that could easily be constructed?
A well-known algorithm for this problem is Dijkstra's algorithm (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). This algorithm picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Has such an algorithm ever been implemented in Gremlin, or is it something that could easily be constructed?
I have tried the solution proposed in https://stackoverflow.com/questions/54887916/gremlin-sort-shortest-weighted-path-output-by-cost on the famous air-routes graph, but in AWS Neptune I get a "MemoryLimitExceededException" error:
g.V("687").repeat(outE().inV().simplePath()).until(hasId("1343")).
path().as('p').
map(unfold().coalesce(values('dist'),
constant(0.0)).sum()).as('cost').
order().by(select('cost')).
select('cost','p')
Does someone know a better way to do this?
Thanks in advance for your help!
HadoopMarc
Mar 22, 2021, 2:58:52 AM3/22/21
to Gremlin-users
Hi Ariel,
You do not need the order()by(), but you can rather use reaching the final vertex as the termination condition for the loop. see:
Best wishes, Marc
Op zondag 21 maart 2021 om 11:32:26 UTC+1 schreef ariel....@wishtrip.com:
Ariel deGraaf
Mar 22, 2021, 4:00:58 AM3/22/21
to gremli...@googlegroups.com
Thank you so much, Marc!
It works like a charm now:
g.V("687").repeat(outE().inV().simplePath()).until(hasId("1343")).
path().as('p').
map(unfold().coalesce(values('dist'),
constant(0.0)).sum()).as('cost').
path().as('p').
map(unfold().coalesce(values('dist'),
constant(0.0)).sum()).as('cost').
limit(1).
select('cost','p')
--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/2f430e7e-b6b9-4dc7-8533-10ed79d9fa3bn%40googlegroups.com.
HadoopMarc
Mar 22, 2021, 9:40:39 AM3/22/21
to Gremlin-users
Now, I see this back, I realize that this does not give a full answer to Dijkstra's algorithm. Before checking the existence of a TinkerPop recipe, I wanted to answer the following:
rather than storing ***all paths*** and finding the path with the smallest cost using order().by(), you can follow ***all paths*** and store only paths that have a lower cost than the best path uptil that point. Relevant steps are choose(), aggregate() and cap(), apart from the steps already present.
Best wishes, Marc
Op maandag 22 maart 2021 om 09:00:58 UTC+1 schreef ariel....@wishtrip.com:
Reply all
Reply to author
Forward
0 new messages