# Recurring search too complex for me

**URL:** <https://www.ruby-forum.com/t/recurring-search-too-complex-for-me/109099>\
**Category:** Ruby\
**Created:** [July 11, 2007, 3:24pm UTC](https://www.ruby-forum.com/t/recurring-search-too-complex-for-me/109099 "2007-07-11T15:24:47Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Josselin](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/9de0a6/32.png) [@Josselin](https://www.ruby-forum.com/u/Josselin)\
**Post date:** [July 11, 2007, 3:24pm UTC](https://www.ruby-forum.com/t/recurring-search-too-complex-for-me/109099/1 "2007-07-11T15:24:47Z")

</div>

even if I am progressing, I’m still a newbie…

I need you advice on doing the follwing search

from an object \<:id =\> 25\> I would like to get the path up to another  
object, ex \<:id =\> 81\>  
using a :parent\_collection to get up into the tree

my structure can be described accoding to this pattern

{id =\> 25, :parent\_collection =\> [25,32,43,53], :data =\> “data25”}  
{id =\> 26, :parent\_collection =\> [26,11,10,9], :data =\> “data26”}  
… and more  
{id =\> 43, :parent\_collection =\> [19,43,54,32], :data =\> “data43”}  
{id =\> 44, :parent\_collection =\> [5,44,8], :data =\> “data44”}  
… and more  
{id =\> 54, :parent\_collection =\> [54, 81,12,18], :data =\> “data54”}  
{id =\> 55, :parent\_collection =\> [55,100,102], :data =\> “data55”}  
… and more

result in this case is :  
path = [25, 43, 54, 81]

this is trying to find a path in a tree between 2 objects… does it  
exist a lib to do such searches ?

thanks for your help

joss

---

<div class="post-metadata">

**Author:** ![Josselin](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/9de0a6/32.png) [@Josselin](https://www.ruby-forum.com/u/Josselin)\
**Post date:** [July 11, 2007, 4:36pm UTC](https://www.ruby-forum.com/t/recurring-search-too-complex-for-me/109099/2 "2007-07-11T16:36:05Z")

</div>

Dear Josselin,

if I understand you correctly, you are looking for  
are solution to a path-finding problem in a graph -  
so Dijkstra’s algorithm can do this for you.  
There is a nice example of finding a shortest path between  
several cities illustrating how the algorithm works here:

> **[Algorithme de Dijkstra](https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra)**
>
> Pour un graphe à 
>   
> n
> n
>   
> sommets et 
>   
> m
> m
>   
> arcs :
>  
>   
>     
>       
> O
> (
> (
> n
> +
> m
> )
> log
> ⁡
> (
> n
> )
> )
>       
>     
> {\\displaystyle O((n+m)\\log(n))}
>   
> pour l'implémentation avec un tas binaire,
> modifier - modifier le code - modifier Wikidata En théorie des graphes, l'algorithme de Dijkstra (prononcé \[dɛɪkstra\]) sert à résoudre le problème du plus court chemin. Il permet, p...

(unfortunately, the English wikipedia doesn’t have this  
example, but from your email address I assume you read French anyway).  
You can find an implementation of Dijkstra’s algorithm,  
as well as many other graph algorithms, here:

[http://gratr.rubyforge.org/](http://gratr.rubyforge.org/)

Best regards,

Axel